最大公約数
시간 제한8초메모리 제한1024 MB
1 ≤ x < M이고 M과 x가 서로소이며 Ax ≡ gcd(M,A) (mod M)을 만족하는 x의 개수를, M이 10^12까지인 최대 500개의 데이터셋에 대해 구한다.
문제
正の整数 M, A が与えられる．整数 x が以下の条件をすべて満たすとき，x は良い整数である．良い整数の個数を求めよ．
- 1 ≤ x < M．
- M と x は互いに素．
- M と A の最大公約数を g とするとき，Ax ≡ g (mod M)．
입력
入力は 500 個以下のデータセットからなる．各データセットは次の形式で表される．
M A
各データセットは整数 M と A を含む 1 行からなる．2 ≤ M ≤ 1012 および 1 ≤ A < M を満たすことが保証される．
入力の終わりは 2 つのゼロからなる行で表される．
출력
各データセットに対し，良い整数の個数を 1 行に出力せよ．