hdu 2588 歐拉函數

連結：戳這裡

GCD

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

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。找出gcd(n,a)>=m (1<=a<=n) 滿足條件的a有多少個

思路：

首先定義數a能被n整除，且a>=m

對于1~n中肯定有許多是a的倍數同樣也滿足條件 gcd(a*p,n)=a，a>=m  這裡的p顯然與n/a互質。

歐拉函數計算(1~n/a)素數的個數算貢獻

我們來證明為什麼是計算與n/a互質 且 貢獻沒有多餘的計算

假設p與n/a不互質，那麼gcd(a*p,n)=a，=> (除以a) gcd(p,n/a)!=1 顯然與我們想要的gcd(a*p,m)=a沖突

是以這個數p必然與n/a互質

好，那為什麼是算n/a與p互質的個數的貢獻呢？

現在gcd(a*p,n)=a，a>=m 需要滿足條件，這裡的p的取值範圍1~n/a之間的，且必須與(n/a)互質

也就是貢獻加上euler(n/a)的值了

那麼接下來證明為什麼沒有計算多餘的貢獻？

設a、b為兩個不同的大于等于m的n的約數

假設存在重複 那麼就有 a*x = b*y (x是小于等于n/a且與n/a互質的數，y同理)

變形 得到 x*n/b = y*n/a 由于x和n/a互質 是以 x是y的約數（因為兩邊分解質因數的時候n/a不能分出x的約數 隻能是y來分）

不妨設 y = kx（k>1）  則 n/b = k(n/a)

由于y和n/b互質 則kx和n/b互質 但是n/b有個k作為約數 是以他們有公約數k 這顯然推出k = 1 于是産生a==b沖突！

是以不會産生重複

代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include <ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<iomanip>
#include<cmath>
#include<bitset>
#define mst(ss,b) memset((ss),(b),sizeof(ss))
///#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long ll;
typedef long double lb;
#define INF (1ll<<60)-1
#define Max 1e9
using namespace std;
int euler(ll n){
    int res=n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            res=res*(i-1)/i;
            while(n%i==0) n/=i;
        }
    }
    if(n>1) res=res*(n-1)/n;
    return res;
}
int main(){
    int T;
    scanf("%d",&T);
    int n,m;
    while(T--){
        scanf("%d%d",&n,&m);
        int ans=0;
        if(m==1) {
            printf("%d\n",n);
            continue;
        }
        for(int i=1;i*i<=n;i++){
            if(n%i==0){
                if(i>=m) ans+=euler(n/i);
                if(n/i!=i && n/i>=m) ans+=euler(i);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}