HourRank 3 3問目
problem statement（コンテストページ）
$f(n)$ で $n$ の約数の積と定義する．
例えば，$f(12) = 1 \times 2 \times 3 \times 4 \times 6 \times 12 = 1728$ である．
正整数 $X$ が与えられるので，$f(n) = X$ となる最小の $n$ を求める問題．
ただし，そのような $n$ が存在しないならそれを指摘する．
まず，$X$ の相異なる素因数が $p_1,p_2,\ldots,p_k$ であるとすると，$n$ も $p_1,\ldots,p_k$ の全てを素因数に持ち，その他の素因数を持ってはならない．
また，$n = p_1 p_2 p_3$ ならば，$f(n) = 1 \times p_1 \times p_2 \times p_3 \times p_1 p_2 \times p_1 p_3 \times p_2 p_3 \times p_1 p_2 p_3 = p_1^4 p_2^4 p_3^4 = n^4$ となることから，
$n$ が相異なる素因数が $3$ つ以上含まれる場合は，$f(n)$ の値は少なくても $n^4$ になる．
よって，$n \leq f(\sqrt[4]{10^{18}})$ 程度までは $f(n)$ の値を篩っぽく計算しておいて，メモしておく．
これで，$X$ が相異なる素因数を $3$ つ以上持つ場合は，このメモを参照すれば良い．
$X$ を素因数分解してみて，相異なる素因数が $2$ 個以下の場合は，適当に指数を全探索すれば良い．
つまり，$n = p_1^{j_1} p_2^{j_2}$ として $j_1, j_2$ を探せば良い．
素因数分解はポラードローで間に合ったが，もし変なケース（アンチケース）が入れられていた場合は，TLEになるはずで，その場合は，
$n = p_1$ ならば $f(n) = n$
$n = p_1^2$ ならば $f(n) = p_1^3$
であるので，$X$ が素数ならば $n=X$ とし，そうでないなら，$10^6$ 以下の素数を使って素因数分解できると仮定すれば良い．
（$n = p_1 p_2$ ならば $f(n) = n^2$ になるので，これに該当する場合も，片方は $10^6$ 以下の素数なので，$10^6$ 以下の素数を使って素因数分解できるはずである，残りは平方数かどうかの判定は必要）
（素数判定はミラーラビンなどを用いれば良い）
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
#define ll long long
#define ull unsigned ll
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(double *x){scanf("%lf",x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w){reader(x);reader(y);reader(z);reader(w);}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(double x, char c){printf("%.15f",x);mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
template<class T, class S> void writerLn(T x, S y){writer(x,' ');writer(y,'\n');}
template<class T, class S, class U> void writerLn(T x, S y, U z){writer(x,' ');writer(y,' ');writer(z,'\n');}
template<class T> void writerArr(T x[], int n){int i;if(!n){mypc('\n');return;}rep(i,n-1)writer(x[i],' ');writer(x[n-1],'\n');}
void eratosthenes(int n,int p[]){
int i,j;
p[0]=p[1]=0; REP(i,2,n) p[i]=1;
for(i=4;i<n;i+=2) p[i]=0;
for(i=3;i*i<n;i+=2) if(p[i]) for(j=i;i*j<n;j+=2) p[i*j]=0;
}
int ullNumberOfLeadingZerosTable[256]={8,7,6,6,5,5,5,5,4,4,4,4,4,4,4,4,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
int ullNumberOfLeadingZeros(ull x){
int res=56; unsigned xl=x, xh=x>>32;
if(xh) res -= 32, xl = xh;
if(xl&0xffff0000U) res -= 16, xl >>= 16;
if(xl&0x0000ff00U) res -= 8, xl >>= 8;
return res + ullNumberOfLeadingZerosTable[xl];
}
ull ullMultipleMod(ull x, ull y, ull m){
int k,loop=2;
ull xlo,xhi,ylo,yhi,rlo,rhi,d1,d2,a,q,r,mask=0xffffffffULL;
if(m<=mask) return (x*y)%m;
xlo=(x&mask); xhi=(x>>32);
ylo=(y&mask); yhi=(y>>32);
rhi=xhi*yhi; rlo=xlo*ylo;
a=(rlo>>32)+xhi*ylo;
rhi+=(a>>32); a&=mask; a+=xlo*yhi; rhi+=(a>>32);
rlo = (rlo&mask) | ((a&mask)<<32);
k = ullNumberOfLeadingZeros(m);
rhi = (rhi<<k)|(rlo>>(64-k));
rlo<<=k; m<<=k;
d1=(m>>32); d2=(m&mask);
while(loop--){
r = rhi/d1*d2;
rhi = ( (rhi%d1 << 32) | (rlo>>32) );
rlo = ( (rlo&mask) << 32 );
if(rhi<r) rhi+=m-r; else rhi-=r;
if(rhi>m) rhi+=m;
}
return rhi>>k;
}
ull ullPowMod(ull x, ull k, ull m){
ull res;
if(k==0) return 1;
res = ullPowMod(x,k/2,m);
res = ullMultipleMod(res,res,m);
if(k%2) res = ullMultipleMod(res,x,m);
return res;
}
ull unsignedMillerRabinSuspectPow(int a, unsigned k, unsigned n){
ull p=1; unsigned bit;
for (bit=0x80000000U;bit;bit>>=1) {
if(p>1) p=(p*p)%n;
if(k&bit) p=(p*a)%n;
}
return p;
}
int unsignedMillerRabinSuspect(int b, unsigned n){
unsigned i,t=0,u=n-1; ull now, next;
while(!(u&1)) t++, u>>=1;
now = unsignedMillerRabinSuspectPow(b, u, n);
for(i=1;i<=t;i++){
next=(now*now)%n;
if(next==1 && now!=1 && now!=n-1) return 0;
now=next;
}
return next==1;
}
int unsignedMillerRabin(unsigned n){
if(n<=1)return 0; if(n<=3)return 1; if(!(n&1))return 0;
if(!unsignedMillerRabinSuspect(2,n)) return 0;
if(n<=1000000){
if(!unsignedMillerRabinSuspect(3,n)) return 0;
} else {
if(!unsignedMillerRabinSuspect(7,n)) return 0;
if(!unsignedMillerRabinSuspect(61,n)) return 0;
}
return 1;
}
ull ullMillerRabinSuspectPow(ull a, ull k, ull n){
ull p=1, bit;
for (bit=0x8000000000000000ULL;bit;bit>>=1) {
if(p>1) p=ullMultipleMod(p,p,n);
if(k&bit) p=ullMultipleMod(p,a,n);
}
return p;
}
int ullMillerRabinSuspect(ull b, ull n){
ull i, t=0, u=n-1, now, next;
while(!(u&1)) t++, u>>=1;
now = ullMillerRabinSuspectPow(b, u, n);
for(i=1;i<=t;i++){
next=ullMultipleMod(now,now,n);
if(next==1 && now!=1 && now!=n-1) return 0;
now=next;
}
return now==1;
}
int ullMillerRabin(ull n){
int i,lim;
if(n<(1ULL<<32)) return unsignedMillerRabin(n);
if(!(n&1)) return 0;
if(n < 341550071728321ULL) lim=17; else lim=29;
if(!ullMillerRabinSuspect(2,n)) return 0;
for(i=3;i<=lim;i+=2) if(!ullMillerRabinSuspect(i,n)) return 0;
return 1;
}
unsigned unsignedGCD(unsigned a,unsigned b){unsigned r; while(a){r=b; b=a; a=r%a;} return b;}
ull ullGCD(ull a,ull b){ull r; while(a){r=b; b=a; a=r%a;} return b;}
#define RHO_PRIME_MAX 120
#define RHO_FIRST_DIVISION_TRIAL_NUMBER 30
#define RHO_NUMBER_OF_ITERATION 50000
#define RHO_UNSIGNED_NUMBER_OF_ITERATION 1000
int rhoIsPrime[RHO_PRIME_MAX], rhoPrimeSize, rhoPrimeArray[RHO_PRIME_MAX];
void rhoInit(){
int i;
eratosthenes(RHO_PRIME_MAX,rhoIsPrime);
rhoPrimeSize=0;
REP(i,2,RHO_PRIME_MAX) if(rhoIsPrime[i]) rhoPrimeArray[rhoPrimeSize++]=i;
}
int ullFactorizationTrialDivision(ull n,ull res[]){
int i,ef=0,size=0;
if(n < RHO_PRIME_MAX && rhoIsPrime[n]){res[0]=n; return 1;}
rep(i,rhoPrimeSize){
if( (ull)rhoPrimeArray[i]*rhoPrimeArray[i] > n ){ef=1; break;}
while(n%rhoPrimeArray[i]==0) res[size++]=rhoPrimeArray[i], n/=rhoPrimeArray[i];
}
if(!ef) for(i=RHO_PRIME_MAX;;i++){
if( (ull)i*i > n ) break;
while(n%i==0) res[size++]=i, n/=i;
}
if(n>1) res[size++]=n;
return size;
}
unsigned unsignedFactorizationPollardRhoSubFind(unsigned n,unsigned parameter){
ull x=2,y=2,memo=1; unsigned d=1; int count=0, next=2, interval=2, next_interval=3;
while(d==1){
if(count++ > RHO_UNSIGNED_NUMBER_OF_ITERATION) return 0;
x=(x*x)%n; if(x<n-parameter) x+=parameter; else x-=n-parameter;
if(!interval){
d=unsignedGCD(memo,n); interval=next_interval++;
if(x>y) memo=x-y; else memo=y-x;
} else {
if(x>y) memo=(memo*(x-y))%n; else memo=(memo*(y-x))%n;
}
if(count==next) y=x, next<<=1;
interval--;
}
if(d==n) return 0;
return d;
}
int unsignedFactorizationPollardRhoMain(unsigned n,ull res[]){
int m,size=0; unsigned fin;
if(n <= 1) return 0;
if(n < RHO_PRIME_MAX && rhoIsPrime[n]){res[0]=n; return 1;}
if(RHO_PRIME_MAX <= n && unsignedMillerRabin(n)){res[0]=n; return 1;}
fin = unsignedFactorizationPollardRhoSubFind(n,1);
if(!fin) fin = unsignedFactorizationPollardRhoSubFind(n,3);
if(!fin) fin = unsignedFactorizationPollardRhoSubFind(n,31);
if(!fin) fin = unsignedFactorizationPollardRhoSubFind(n,63);
if(!fin) fin = unsignedFactorizationPollardRhoSubFind(n,107);
if(!fin) fin = unsignedFactorizationPollardRhoSubFind(n,121);
if(!fin) {res[0]=n; return 1;}
size+=unsignedFactorizationPollardRhoMain(fin,res+size);
size+=unsignedFactorizationPollardRhoMain(n/fin,res+size);
return size;
}
ull ullFactorizationPollardRhoSubFind(ull n,ull parameter){
ull x=1,y=1,d=1,memo=1; int count=0, next=2, interval=9, next_interval=10;
while(d==1){
if(count++ > RHO_NUMBER_OF_ITERATION) return 0;
x=ullMultipleMod(x,x,n); if(x<n-parameter) x+=parameter; else x-=n-parameter;
if(!interval){
d=ullGCD(memo,n); interval=next_interval++;
if(x>y) memo=x-y; else memo=y-x;
} else {
if(x>y) memo=ullMultipleMod(memo,x-y,n); else memo=ullMultipleMod(memo,y-x,n);
}
if(count==next) y=x, next<<=1;
interval--;
}
if(d==n) return 0;
return d;
}
int ullFactorizationPollardRhoMain(ull n,ull res[]){
int m,size=0; ull fin=0;
if(n < (1ULL<<32)) return unsignedFactorizationPollardRhoMain(n,res);
if(/*n < 341550071728321ULL && */ullMillerRabin(n)){res[0]=n; return 1;}
fin = ullFactorizationPollardRhoSubFind(n,1);
if(!fin) fin = ullFactorizationPollardRhoSubFind(n,3);
if(!fin) fin = ullFactorizationPollardRhoSubFind(n,39);
if(!fin) fin = ullFactorizationPollardRhoSubFind(n,67);
if(!fin) {res[0]=n; return 1;}
size+=ullFactorizationPollardRhoMain(fin,res+size);
size+=ullFactorizationPollardRhoMain(n/fin,res+size);
return size;
}
int ullFactorizationPollardRho(ull n,ull res[]){
int i,size=0;
rep(i,RHO_FIRST_DIVISION_TRIAL_NUMBER){
if( rhoPrimeArray[i]*rhoPrimeArray[i] > n ) break;
while(n%rhoPrimeArray[i]==0) n/=rhoPrimeArray[i], res[size++]=rhoPrimeArray[i];
}
return size+ullFactorizationPollardRhoMain(n,res+size);
}
template<class T> void sort(int N, T a[], void *mem = NULL){sort(a,a+N);}
template<class T1, class T2> void sort(int N, T1 a[], T2 b[], void *mem){int i;pair<T1,T2> *r=(pair<T1, T2>*)mem;rep(i,N)r[i].first=a[i],r[i].second=b[i];sort(r,r+N);rep(i,N)a[i]=r[i].first,b[i]=r[i].second;}
template<class T1, class T2, class T3> void sort(int N, T1 a[], T2 b[], T3 c[], void *mem){int i;pair<T1,pair<T2,T3> > *r=(pair<T1,pair<T2,T3> >*)mem;rep(i,N)r[i].first=a[i],r[i].second.first=b[i],r[i].second.second=c[i];sort(r,r+N);rep(i,N)a[i]=r[i].first,b[i]=r[i].second.first,c[i]=r[i].second.second;}
template<class T1, class T2, class T3, class T4> void sort(int N, T1 a[], T2 b[], T3 c[], T4 d[], void *mem){int i;pair<pair<T1,T2>,pair<T3,T4> > *r=(pair<pair<T1,T2>,pair<T3,T4> >*)mem;rep(i,N)r[i].first.first=a[i],r[i].first.second=b[i],r[i].second.first=c[i],r[i].second.second=d[i];sort(r,r+N);rep(i,N)a[i]=r[i].first.first,b[i]=r[i].first.second,c[i]=r[i].second.first,d[i]=r[i].second.second;}
template<class T> void unique(T arr[], int &sz, int sorted=0){int i,k=0;if(!sorted)sort(arr,arr+sz);rep(i,sz)if(!k||arr[k-1]!=arr[i])arr[k++]=arr[i];sz=k;}
template<class T, class S> void unique(T arr[], S val[], int &sz, void *mem, int sorted=0){int i,k=0;if(!sorted)sort(sz,arr,val,mem);rep(i,sz)if(!k||arr[k-1]!=arr[i])arr[k]=arr[i],val[k++]=val[i];else val[k-1] += val[i];sz=k;}
template<class T, class S, class V> void unique(T arr[], S v1[], V v2[], int &sz, void *mem, int sorted=0){int i,k=0;if(!sorted)sort(sz,arr,v1,v2,mem);rep(i,sz)if(!k||arr[k-1]!=arr[i])arr[k]=arr[i],v1[k]=v1[i],v2[k++]=v2[i];else v1[k-1] += v1[i],v2[k-1] += v2[i];sz = k;}
char memarr[17000000]; void *mem = memarr;
#define MD 1000000007
#define INF 2000000000000000000LL
inline ull mul(ull a, ull b){
if((double)a*b > INF) return INF;
return a*b;
}
ull pw(ull a, ull b){
int i;
ull res = 1;
rep(i,b) res = mul(res,a);
return res;
}
int T;
ll X;
map<ll,ll> cal;
ll memo[1000001];
int main(){
int i, j, k;
ull fac[100]; int num[100]; int fs;
ll res, tmp, tmp1, tmp2;
rep(i,1000001) memo[i] = 1;
REP(i,2,1000001) for(j=i;j<=1000000;j+=i) memo[j] = mul(memo[j], i);
REP(i,1,1000001){
if(memo[i]>=INF) continue;
if(cal.count(memo[i])==0) cal[memo[i]] = i;
}
rhoInit();
reader(&T);
while(T--){
reader(&X);
if(cal.count(X)){
writerLn(cal[X]);
continue;
}
fs = ullFactorizationPollardRho(X, fac);
rep(i,fs) num[i] = 1;
unique(fac, num, fs, mem);
sort(fs, num, fac, mem);
if(fs==1){
k = 0;
for(i=1;;i++){
k += i;
if(k > num[0]){
writerLn(-1);
break;
} else if(k==num[0]){
res = pw(fac[0], i);
writerLn(res);
break;
}
}
continue;
}
if(fs==2){
k = 0;
rep(i,40) if(!k) REP(j,i,40) if(!k){
tmp1 = pw(fac[0], i*(i+1)/2*(j+1));
if(tmp1 >= INF) break;
tmp2 = pw(fac[1], j*(j+1)/2*(i+1));
tmp = mul(tmp1, tmp2);
if(tmp >= INF) break;
if(tmp == X){
res = pw(fac[0], i) * pw(fac[1], j);
writerLn(res);
k = 1;
break;
}
}
if(k==0) writerLn(-1);
continue;
}
writerLn(-1);
}
return 0;
}
Current time: 2024年04月24日00時25分13秒
Last modified: 2015年12月12日01時50分37秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_hourrank-3
トップページに戻る
Logged in as: unknown user (not login)