hdu 2588 GCD

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2346    Accepted Submission(s): 1193

Problem Description

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.

 

Input

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.

 

Output

For each test case,output the answer on a single line.

 

Sample Input

3 1 1 10 2 10000 72

 

Sample Output

1 6 260

 

Source

 

 

题意：求解小于n的数i且gcd（i，n）大于m的i的个数

分析：

对于所有小于n的最大公约数值一定是n的因子，所以，从这个方面下手找i为n的因子且i>m时求解车i的素数倍数且小于n的个数累加起来就好了。以为这个倍数最大为n/i所以求得n/i的欧拉函数值累加起来就好了。

借(piao)鉴(qie)自http://blog.csdn.net/qq_27599517/article/details/50950218

屠龙宝刀点击就送

#include <ctype.h>
#include <cstdio>

void read(int &x)
{
    x=0;bool f=0;
    register char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=1;
    for(; isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    x=f?(~x)+1:x;
}
int T;
int get_phi(int n)
{
    if(n==1) return 1;
    int ans=n;
    if(n%2==0)
    {
        while(n%2==0) n/=2;
        ans/=2;
    }
    for(int i=3;i*i<=n;i+=2)
    {
        if(n%i==0)
        {
            while(n%i==0) n/=i;
            ans=ans/i*(i-1);
        }
    }
    if(n>1)
        ans=ans/n*(n-1);
    return ans;
}
int main()
{
    read(T);
    for(int n,m;T--;)
    {
        read(n);
        read(m);
        long long ans=0;
        for(int i=1;i*i<=n;i++)
        {
            if(n%i==0)
            {
                if(i>=m&&n/i!=i)
                ans+=get_phi(n/i);
                if(n/i>=m)
                ans+=get_phi(i);
            }
        }
        printf("%lld
",ans);
    }
    return 0;
}