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;
}