Day1

数论共产党$gcd$，欧拉函数

CF-1295D

题意：

给定两个整数$a$和$m$，计算使得$gcd(a+x,m)=gcd(a,m) \ (0\le x \le m \ \ 1\le a < m \le 10^{10} )$成立的$x$的数量

题解：

如果$a\ge b$，$gcd(a,b)=gcd(a-b,b)$

如果$a+x \ge m$

那么$gcd(a+x,m)=gcd(a+x-m,m)$

$a+x-m=(a+x)%m$

$x’=(a+x)%m \ (0 \le x’ < m)$

$gcd(x’,m)=gcd(a,m)=d$

$gcd(\frac{x’}{d},\frac{m}{d})=1$

答案就是在区间$(0,\frac{m}{d}]$中与$\frac{m}{d}$互质的个数，即$\varphi (\frac{m}{d})$。

#include<cstdio>
#include<vector>
#include<iostream>
#include<cstring>
#include<ctime>
#include<map>
#include<algorithm>
#include<cmath>
#define F first
#define S second
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
ll phi(ll n){
    ll i,rea=n;
    for(i=2;i*i<=n;i++){
        if(n%i==0){
            rea=rea-rea/i;
            while(n%i==0)
                n/=i;
         }
    }
    if(n>1)
        rea=rea-rea/n;
    return rea;
}
void solve(){
    ll a,m,d;
    scanf("%lld %lld",&a,&m);
    d=__gcd(a,m);
    printf("%lld\n",phi(m/d));
}
int main(){
    int T_T=1;
    clock_t t0=clock();
    scanf("%d",&T_T);
    while(T_T--){
        solve();
    }
    clock_t t1=clock();
    //printf("%.3fms\n",(double)(t1-t0)/CLOCKS_PER_SEC*1000.0);
}