https://codeforces.com/contest/1295/problem/D
B풀다가 시간 다가버린 참교육 라운드
<문제설명>
1 <= a < m < 10e10, 0<=x<m
gcd(a,m) = gcd(a+x,m)을 만족하는 정수 x의 개수를 구하여라
<풀이>
gcd(a,m) = g 이라고 하자.
gcd(a+x,m) = gcd( m, (a+x)%m )에서 (a+x)%m은 [0,m) 값을 모두 가질 수 있다.
따라서 x의 개수는 [0,m)범위의 정수 중 m과 최대공약수가 g인 것의 개수와 같다.
다시말하면, [0,m)범위의 정수 중 m/g와 서로소인 것의 개수를 구하면 된다.
답은 phi(m/g)
<코드>
ll gcd(ll a, ll b) {
if (a < b) swap(a, b);
if (b == 0) return a;
return gcd(b, a % b);
}
int main() {
FAST;
int tt; cin >> tt;
while (tt--) {
ll a, m; cin >> a >> m;
m /= gcd(a, m);
ll phi = m;
for (ll i = 2; i * i <= m; i++) {
if (m % i == 0) {
phi /= i;
phi *= (i - 1);
}
while (m % i == 0) m /= i;
}
if (m != 1) {
phi /= m;
phi *= (m - 1);
}
cout << phi << '\n';
}
}
<생각>
소인수분해와 오일러 피함수에 대해서 언젠간 공부해야지 싶었는데, 공부하는 계기가 된 문제