Factorial: 階乗

解法

  • nを素因数分解して
  • p1^e1*p2^e2*p3^e3*......pr^erとなったとき、 m1!%p1^e1==0,m2!%p2^e2,m3!%p3^e3,.....となる
  • 最小のm1,m2,m3...を求めて
  • m1,m2,m3....の中で最も大きな値が答え
#include <stdio.h>
#include <vector>
#include <map>
using namespace std;
typedef long long LL;
vector<pair<LL,int> > primeFactor(LL num){ //first->prime,second->pow{
	if(num==1){
		vector<pair<LL,int> > r;
		r.push_back(make_pair(1,1));
		return r;
	}
	else{
		vector<pair<LL,int> > r;
		for(LL i=2;i*i<=num;i++){
			if(num%i==0){
				int p=0;
				while(num%i==0)
					num/=i,p++;
				r.push_back(make_pair(i,p));
			}
		}
		if(num!=1)
			r.push_back(make_pair(num,1));
		return r;
	}
}
int main(){
	LL n;
	scanf("%lld",&n);
	vector<pair<LL,int> > ps=primeFactor(n);
	LL res=0;
	for(int i=0;i<(int)ps.size();i++){
		LL a=0,b=ps[i].second;
		while(0<b){
			a+=ps[i].first;
			for(LL t=ps[i].first;a%t==0;t*=ps[i].first)
				b--;
		}
		res=max(res,a);
	}
	printf("%lld\n",res);
	return 0;
}