2545 Hamming Problem

PKU

三つの異なる素数p,q,rが渡され、p^iq^jr^kで表される自然数(min(i,j,k)>0)を小さい方から数えていくとき、s番目の数字を表示するというもの。
入出力の数字は10^18未満とかなりでかいが、64ビット非負整数で表せるので使う。
ただし、C(Visual C++ 6.0)とGCC(MinGW)では取り扱いが違うので注意。知らないとはっきり言って問題を解くのよりもよっぽど難しい。
別に短くはしていないが、通ったコードを見たい人はどうぞ。
Cの場合

unsigned __int64 z[99999],a,b,c,t,u,v,i,x;
p,q,r,s;
main(){
  scanf("%I64u%I64u%I64u%I64u",&a,&b,&c,&i);
  for(z[0]=1;s<i;)
    t=z[p]*a,u=z[q]*b,v=z[r]*c,x=t>u?u>v?v:u:t>v?v:t,z[++s]=x,p+=x==t,q+=x==u,r+=x==v;
  printf("%I64u\n",z[i]);
}

GCCの場合

unsigned long long z[99999],a,b,c,t,u,v,i,x;
p,q,r,s;
main(){
  scanf("%llu%llu%llu%llu",&a,&b,&c,&i);
  for(z[0]=1;s<i;)
    t=z[p]*a,u=z[q]*b,v=z[r]*c,x=t>u?u>v?v:u:t>v?v:t,z[++s]=x,p+=x==t,q+=x==u,r+=x==v;
  printf("%I64u\n",z[i]);
}

まとめ

  • Cでは__int64を、GCCではlong longを使う。
  • scanfは"%llu"でもOK。printfは"%llu"ではだめ。