CodeForces - 1295D Same GCDs （欧拉函数）

传送门：CodeForces - 1295D

题目描述

You are given two integers $a$ and $m$. Calculate the number of integers $x$ such that $0≤x<m$ and $gcd(a,m)=gcd(a+x,m)$.

输入描述

The first line contains the single integer $T$ $(1≤T≤50)$ — the number of test cases.

Next $T$ lines contain test cases — one per line. Each line contains two integers $a$ and $m$ $(1≤a<m≤10^{10})$.

输出描述

Print $T$ integers — one per test case. For each test case print the number of appropriate $x-s$.

思路分析

借鉴网上的题解，数论题确实恼火：

• 给出两个正整数 $a$ 和 $m$ ，再给出 $x$ 的范围为 $[0,m)$，现在要求满足 $gcd(a,m)=gcd(a+x,m)$ 时 $x$ 的个数。
• 首先提取 $a$ 和 $m$ 的最大公约数$g$，令 $a=xg$ , $m=yg$
• 题意就可以转化为使得 $gcd(xg,yg)=gcd(xg+z,yg)=g$
• 显然可知 $z$ 为 $g$ 的倍数，令$z=kg$, $k\in[0,y)$
• 那么所有满足 $gcd(x+k,y)=1$ 的 $k$ 都可以，即求 $[x,x+y)$ 中与 $y$ 互质的个数
• 因为$gcd(x,y)=gcd(y,y%x)$，故当 $x+k \in (y,x+y)$ 时，$gcd(x+k,y)=gcd(y,(x+k)%y)$
• 因为 $x<y$，$k \in [0,y)$，所以$gcd(x+k,y)=gcd(y,(x+k)-y)=1$
• 而$x+k-y \in (0,x)$
• 所以$(y,x+y)$中与$y$互质的个数与$(0,x)$中与$y$互质的个数相等

所以答案就是$[1,y)$中，与$y$互质的个数，也就是欧拉函数。

样例输入

3
4 9
5 10
42 9999999967

样例输出

6
1
9999999966

AC代码

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls ro<<1
#define fi first
#define se second
#define rs ro<<1|1
#define ll long long
#define pb push_back
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define lson ro<<1,l,mid
#define umap unordered_map
#define uset unordered_set
#define rson ro<<1|1,mid+1,r
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;

ll phi(ll n){
       ll m=n;
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0) //第一次找到的必为素因子
        {
            m-=m/i; //把是素因子i的倍数的数的数目减掉  i,2i,3i,···,(m/i)*i
            while(n%i==0)
                n/=i; //把该素因子全部约掉
        }
    }
    if(n>1) //还有一个比根号n大的素因子 ,也就是现在这个n
        m-=m/n;
    return m;
}

int main() {
    IOS;
#ifdef xiaofan
    freopen("in.txt","r",stdin);
#endif

    int t;
    cin>>t;
    while(t--){
        ll a,m;
        cin>>a>>m;
        cout<<phi(m/__gcd(a,m))<<endl;
    }




    return 0;
}
&nbsp;