A. Finite or not? | Codeforces Round #483 (Div. 1)
ll p, q, b; cin >> p >> q >> b; ll g = gcd(p, q); // とりあえず約分 q /= g; // 分母をb^kの形にできればOK // そのためには分母qをgcd(b, q)で割り続けて // bと互いに素な素因数をもつかどうか判定する string re = "Finite"; while (q > 1) { ll h = gcd(q, b); if (h == 1) { re = "Infinite"; break; } // 1秒しかないのでgcdの呼び出し回数を減らす工夫 // while(q%h==0)の部分を取り除くとTLE while(q%h==0)q /= h; } cout << re << endl;