变相欧拉

标签：int cin getans 变相 ret ans integer 欧拉

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.

输入样例

3
1 1
10 2
10000 72
 

输出样例

1
6
260

即 gcd(a,b) = m 对式子做一个简单的变化，同除m，即得到 gcd(a/m,b/m) = 1 也就是求b 除以一个大于等于m的因子后，比它小且与它互质的数有多少个

#include<bits/stdc++.h>

typedef long long LL;
const int MAXN = 3e6 + 10;
using namespace std;

int T;
int a,b;
LL ans;

int getans(int x)
{
    int ret = x;
    for(int i=2;i*i<=x;i++)
    {
        if(x % i == 0)
        {
            ret = ret - ret / i;
            while(x % i == 0) x /= i;    
        }    
    }
    if(x > 1) ret = ret - ret / x;
    return ret;    
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>T;
    while(T--)
    {
        cin>>a>>b;
        ans = 0;
        for(int i=1;i*i<=a;i++)
        {
            if(a % i == 0)
            {
                if(i >= b) ans += getans(a / i);
                if(a / i != i && a / i >= b) ans += getans(i);
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

View Code

 

标签：int,cin,getans,变相,ret,ans,integer,欧拉
From： https://www.cnblogs.com/xxx3/p/17225479.html