HDU2588

题目：click 题意：设g=gcd(X,N),X=$g\ast a$ , N=$g\ast b$,由于N>=X,b>=a,可以直接去枚举约数g，由于gcd(a,b)=1，a<=b，直接欧拉函数求可得。

#include<cmath> #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cstdlib> #include<istream> #include<vector> #include<stack> #include<set> #include<map> #include<algorithm> #include<queue> #define inf 0x3f3f3f3f #define llinf 0x3f3f3f3f3f3f3f3f #define MAX_len 200005*4 using namespace std; typedef long long ll; typedef pair<int,int> PP; const int mod=998244353; const int MAXlen=1e5+10; long double eps=1e-9; ll euler(ll n) { ll i,j,res=n,temp=n; for(i=2;i*i<=temp;i++) { if(temp%i==0) { res=res/i*(i-1);//先进行除法是为了防止中间数据爆范围 while(temp%i==0) temp/=i; } } if(temp>1) res=res/temp*(temp-1); return res; } int main() { int T; scanf("%d",&T); while(T--) { ll ans=0; ll n,i,m,j; scanf("%lld %lld",&n,&m); for(i=1;i*i<=n;i++) { if(i*i==n&&i>=m) { ans+=euler(i); continue; } if(i>=m&&n%i==0) { ans+=euler(n/i); } if(n%i==0&&n/i>=m) { ans+=euler(i); } } printf("%lld\n",ans); } return 0; }