HackerRank HourRank 3 3問目 - Professor Numerico and the Divisors

Source

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$ 以下の素数を使って素因数分解できるはずである,残りは平方数かどうかの判定は必要)
(素数判定はミラーラビンなどを用いれば良い)

C++によるスパゲッティなソースコード

#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: 2017年11月19日12時16分14秒
Last modified: 2015年12月12日01時50分37秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_hourrank-3
トップページに戻る

Logged in as: unknown user (not login)

ログイン: