1 second
256 megabytes
standard input
standard output
You are given several queries. Each query consists of three integers pp, qq and bb. You need to answer whether the result of p/qp/q in notation with base bb is a finite fraction.
A fraction in notation with base bb is finite if it contains finite number of numerals after the decimal point. It is also possible that a fraction has zero numerals after the decimal point.
The first line contains a single integer nn (1≤n≤1051≤n≤105) — the number of queries.
Next nn lines contain queries, one per line. Each line contains three integers pp, qq, and bb (0≤p≤10180≤p≤1018, 1≤q≤10181≤q≤1018, 2≤b≤10182≤b≤1018). All numbers are given in notation with base 1010.
For each question, in a separate line, print Finite if the fraction is finite and Infinite otherwise.
2
6 12 10
4 3 10
Finite
Infinite
4
1 1 2
9 36 2
4 12 3
3 5 4
Finite
Finite
Finite
Infinite
612=12=0,510612=12=0,510
43=1,(3)1043=1,(3)10
936=14=0,012936=14=0,012
412=13=0,13412=13=0,13
这题，看这个分数在b进制下是否为无限循环小数。
一个分数是否为无限循环小数取决于分母。
于是想到这题一定是考虑 分母q 和 进制b 的关系，
于是就是想办法 把分母化为1就不是无限循环小数
temp1 = gcd(q, b);
if (temp1 == 1) break;
while(q % temp1== 0) {
q /= temp1;
}
while一定要加 不然会超时。
#include<bits/stdc++.h> using namespace std;
const int maxn = 3e5 + ;
typedef long long LL;
LL gcd(LL a, LL b ) {
if (b == ) return a;
return gcd(b, a % b);
}
int main() {
int n;
LL p, q, b;
scanf("%d", &n);
while(n--) {
scanf("%lld%lld%lld", &p, &q, &b);
LL g = gcd(p, q);
p = p / g, q = q / g;
LL temp = p / q;
p = p - temp * q;
if (!p) {
printf("Finite\n");
continue;
}
LL temp1;
while() {
temp1 = gcd(q, b);
if (temp1 == ) break;
while(q % temp1== ) {
q /= temp1;
}
}
if (q == ) printf("Finite\n");
else printf("Infinite\n");
}
return ;
}