Educational_Codeforces_Round_81(Rated_for_Div. 2)_D题

• 2020 年 2 月 18 日
• 筆記

题目大意

求$gcd(a, m) = gcd(a+x, m), 0 <= x < m, 1 <= a < m <= 10^{10}$的$x$的个数

题解

已知$a < m, 0 <= x < m$，根据最大公约数的性质$a >= b, gcd(a, b)=gcd(a-b,b)$，所以如果$a+x>=m$那么$gcd(a+x,m)=gcd(a+x-m,m)$即$a+x$可以写成$(a+x)%m$，令$x’=(a+x)%m,0 <= x’ < m$，则有$(x’,m)=(a,m)$，设$(a,m)=d$那么$(x’,m)=d$，那么$(x’/d, m/d)=1$由于$0 <= x’ < m$，那么$0 <= x’/d < m/d$，答案就是求$φ(m/d)$

#include <bits/stdc++.h>  using namespace std;    typedef long long LL;  #define dbg(x) cout << #x"=" << x << endl;  int T;  LL a,m;    void solve(){      cin >> a >> m;      LL n = m/__gcd(a, m);      LL 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);      cout << ans << endl;  }    int main(){     // freopen("in.txt", "r", stdin);      ios::sync_with_stdio(0); cin.tie(0);      cin >> T;      while(T--) solve();      return 0;  }