题目大意:两个正整数 a 和 b 的最大公约数 GCD(a,b),有时写成 (a,b),是 a 和 b 的最大公约数,例如,(1,2)=1,(12,18)=6。
(a,b) 可以很容易地通过欧几里得算法找到。现在 Carp 正在考虑一个更困难的问题:
给定整数 N 和 M,有多少个整数 X 满足 1<=X<=N 和 (X,N)>=M。
思路:假设(X,N)= y,那么(X / y,N / y)= 1 。因为 X <= N,所以 X / y <= N / y ,所以这道题目就变成了求 N / y 的欧拉函数之和。
代码如下:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
int euler(int n){int ret=n;for(int i=2;i*i<=n;i++){if(n%i==0){ret-=ret/i;while(n%i==0) n/=i;}}if(n>1) ret-=ret/n;return ret;
}
signed main(){IOSint _;cin >> _;while(_--){int n,m,ans=0;cin >> n >> m;for(int i=1;i*i<=n;i++){if(n%i==0){if(i>=m) ans+=euler(n/i);if(n/i>=m && i*i!=n) ans+=euler(i);}}cout << ans << endl;}return 0;
}