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;