（hdu2588）GCD（歐拉函數）

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 2320 Accepted Submission(s): 1174

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

題意：兩個整數N，M，問有多少個X滿足條件1<=X<=N且gcd(X,N)>=M

分析：可以直接用歐拉函數求解

#include<cstdio>
#include<cmath>
using namespace std;
int Euler(int n)///歐拉函數求小于等于n的正整數中有多少個數與n互質
{
    int s=n,i;
    for(i=; i<=sqrt(n); i++) 
    if(n%i==)
        {
            s=s/i*(i-);
            while(n%i==) n/=i;
        }
    if(n>) s=s/n*(n-);
    return s;
}
int main()
{
    int t,n,m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        if(m==) {printf("%d\n",n);continue;}
        int num=;
        for(int i=; i*i<=n; i++)
        {
            if(n%i==) //i是n的因子
            {
                if(i>=m)
                    num+=Euler(n/i);
                if(i*i!=n)///避免重複計算n/i的歐拉函數所求值
                {
                    if(n/i>=m)
                        num+=Euler(n/(n/i));
                }
            }
        }
        printf("%d\n",num+);///+1是因為有一個滿足條件的數是n本身
    }
    return ;
}
           

可以用容斥原理寫？ 我試了，時間超限，用隊列和二進制位實作容斥原理都會TLE。。 遞歸？

先把代碼放上來吧。。

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
int n,m;
LL gcd(LL a,LL b)
{
    return b?gcd(b,a%b):a;
}
LL lcm(int m,int n)
{
    return m/gcd(m,n)*n;
}
int solve()
{
    if(m==) return n;
    vector<int>g;
    int i,j;
    for(int i=; i<=n; i++)
    {
        if(n%i==)
        {
            if(i>=m)
                g.push_back(i);
            if(n/i>=m)
                g.push_back(n/i);
        }
    }
    sort(g.begin(),g.end());
    int cnt=;
    for(i=; i<g.size(); i++)
    {
        for(j=; j<i; j++)
            if(g[i]%g[j]==)
                break;
        if(j==i)
            g[cnt++]=g[i];
    }
    int sum=;
    for(int k=; k<(<<cnt); k++)
    {
        int mul=,num=;
        for(int i=; i<cnt; i++)
        {
            if(k&(<<i))
            {
                num++;
                mul=lcm(mul,g[i]);
            }
        }
        if(num&) sum+=n/mul;
        else sum-=n/mul;
    }
    return sum;
    /* LL sum=0,front=0;
    LL k,que[N],t,tmp;
    que[front++]=-1;
    for(LL i=0; i<cnt; i++)
    {
        k=front;
        for(LL j=0; j<k; j++)
        {
            tmp=abs(que[j]);
            t=lcm(tmp,g[i]);
            que[front++]=t/que[j]*abs(que[j])*(-1);
        }
    }
    for(LL i=1; i<front; i++)
    {
        //printf("%d\n",que[i]);
        sum+=n/que[i];
    }
    return sum;*/
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        printf("%d\n",solve());
    }
    return ;
}