CF1295D Same GCDs 题解
题目链接:CF1295D Same GCDs
题意:
求 \[ \sum_{x=0}^{m-1} [\gcd(a, m) = \gcd(a + x, m)] \] 多组测试数据, \(T \leq 50,\ 1 \leq a < m \leq 10^{10}\)
设 \(p=\gcd(a,m)\) ,则原式可化为 \[ \begin{aligned} \sum_{x=0}^{m-1} [\gcd(a+x,m) = p] &= \sum_{x=0}^{m-1}\left[\gcd\left(\frac{a+x}{p},\frac{m}{p}\right)=1\right] \\\\&=\sum_{x=0}^{m-1}\left[\gcd\left(\left(\frac{a+x}{p} \bmod \frac{m}{p}\right),\frac{m}{p}\right)=1\right] \\\\&= \varphi\left(\frac{m}{p}\right) \end{aligned} \] 即求 \[ \varphi\left(\frac{m}{\gcd(a,m)}\right) \] 时间复杂度 \(O(Q\sqrt{n})\)
代码:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)()
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int Euler_phi(int n)
{
int ans=n;
for(int i=2; i<=n/i; i++)
if(n%i==0)
{
ans=ans/i*(i-1);
while(n%i==0) n/=i;
}
if(n>1) ans=ans/n*(n-1);
return ans;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int Q; cin >> Q;
for(int a,m; Q--;)
{
cin >> a >> m;
cout << Euler_phi(m/gcd(a,m)) << '\n';
}
return 0;
}