An integer N is given. You need to find out how many numbers X (1≤X≤N) are there such that GCD(X,N)≤Q. Here GCD means greatest common divisor. N<10^12, Q<50,000. Nが大きいので、全探索なんて、無理だ。GCDと言うと、素数と余り計算に連想したね。ちょっと数学的な公式に変換してみる。 GCD(X,N)<=Qじゃなくて、GCD(X,N)=Qの条件で考えてみよ。そうすると： X=Q*x' N=Q*n' GCD(x',n')=1 と同じ条件に変換する。 これ見ると、X%Q!=0の場合、処理しなくてもいい。 また、NとQをわかっているので、n'を計算できる。また、元の問題をGCD(x',n')=1のx'の数を数え上げる問題に変える。 BF[0] = 0; // BF[i]とは、X=iの時の結果 for (x=1;x<=Q;x++) { if (N%x==0) { n1=N/x; k = (x'の数); BF[x]=BF[x-1]+k; } else { BF[x]=BF[x-1]; } } x'の数の計算はかなり難しい。逆に、x''の数を計算したほうがいい。ただし,x''とはGCD(x'',n')!=1を満たす値である。n'の約数が全部計算できたら、x''の数が計算できる。 |
|
|