HDu-GCD-Euler関数&GCD原理-数論

タイトルの説明
The greatest common divisor GCD(a,b) of two positive integers a and b,sometimes written (a,b),is the largest divisor common to a and b,For example,(1,2)=1,(12,18)=6. (a,b) can be easily found by the Euclidean algorithm. Now Carp is considering a little more difficult problem: Given integers N and M, how many integer X satisfies 1<=X<=N and (X,N)>=M.
入力
The first line of input is an integer T(T<=100) representing the number of test cases. The following T lines each contains two numbers N and M (2<=N<=1000000000, 1<=M<=N), representing a test case.
しゅつりょく
For each test case,output the answer on a single line.
サンプル入力
3 1 1 10 2 10000 72
サンプル出力
1 6 260
補足知識-GCD原理

GCD(a,b)=cであれば、GCD(a/c,b/c)=1が分かる.( GCD(a,b)=c <=> GCD(a/c,b/c)=1 )

はGCD(a,b)=cとする、GCD(a,b*d)=cを望むならば、以上から分かるように、GCD(a/c,(b/c)*d)=1を満たすだけでよい(この制限は、最大公約数の要求を満たす).

問題解

まずGCD(N,X)≡cを解析し,GCD(N/c,X/c)=1,すなわち相互質個数に変換できた.

M=1の場合、Euler関数Eulerが直接呼び出されます.

M≧2の場合、GCD(N,X)=cであり、c≧M,X∈[1,N]であるため、上GCDの原理から、GCD(N/c,X/c)=1であればよいが、GCD(N,X)=cであり、cが最大公約数であることはNのすべての因子であることが知られている.

だから、M以上のNの因子cを列挙し、euler(c)を合計すればよい.

例:N=12,M=3.Nが3以上の因子は3,4,6,12である.先ほど述べたように,c=3,4,6,12を要求すると,GCD(N/c,X/c)=1互質個数に変換できる.はい、コードを見てください.

#include
#include
#include
using namespace std;

int Euler(int n)
{//    
    int m=sqrt(n+0.5);
    int res=n;
    for(int i=2;i<=m;i++){
        if(n%i==0){
            res=res/i*(i-1);
            while(n%i==0) n/=i;
        }
    }
    if(n>1) res=res/n*(n-1);
    return res;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int N,M;
        scanf("%d%d",&N,&M);
        int ans=0;
        for(int i=1;i*i<=N;i++){
            if(N%i==0){
                if(i>=M) ans+=Euler(N/i);
                if(N/i>=M&&N/i!=i) ans+=Euler(i);
            }
        }
        printf("%d
",ans);
    }
}