解法
- 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){
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;
}