传送门
题意：给定，若，求有多少个x满足
题解：如果满足gcd相同则x必须为gcd(a,m)的倍数，设，则若，有多个w满足。因为d是最大公因数所以。到这里（凭借丰富的骗分经验？）就可以直接猜一波答案是phi(v)了。所以求个gcd再求个欧拉函数就完事儿。一开始欧拉函数没写好还T了一发......这次真的是自己把答案猜对的（*—*）
下面证明一下答案：
相当于要证正整数序列上每个长度为v的周期内与v互质的数的个数相等并且它们的分布是和第一个周期[1, v]是相同的。即证，然后充分性和必要性都反证一下就好了。
为什么证明了与v互质的数的分布的周期性就好？因为有了周期性后，可以把询问的区间进行平移。最后和就可以转化为和。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; ll a,m; inline ll read() { ll x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x*f; } inline ll gcd(ll a,ll b) { return !b?a:gcd(b,a%b); } inline ll phi(ll x) { ll ret=1; for (register ll i=2;i*i<=x;++i) if (x%i==0) { ll cur=1; while (x%i==0) { cur*=i; x/=i; } ret*=(i-1)*cur/i; } if (x>1) ret*=x-1; return ret; } int main() { int kase=read(); while (kase--) { a=read(),m=read(); ll v=m/gcd(a,m); printf("%lld\n",phi(v)); } return 0; }
