You are given several queries. Each query consists of three integers p, q and b. You need to answer whether the result of p/q in notation with base b is a finite fraction.
A fraction in notation with base b 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.
Input
The first line contains a single integer n(1≤n≤105) — the number of queries.
Next n lines contain queries, one per line. Each line contains three integers p, q, and b (0≤p≤1018, 1≤q≤1018, 2≤b≤1018). All numbers are given in notation with base 10
.
Output
For each question, in a separate line, print Finite if the fraction is finite and Infinite otherwise.
Examples
Input
2
6 12 10
4 3 10
Output
Finite
Infinite
``
Input
4
1 1 2
9 36 2
4 12 3
3 5 4
Output
Finite
Finite
Finite
Infinite
@galencolin Please help in this I don’t understand how for 4/12 = 0.33333 in base 3 is finite can u please explain (first clearly question then approach).
Problem_Link
0.1 in base 3 = 3^(-1) in base 10
It is similar to binary to decimal conversions.
0.1 in base 3 = 0.333333333333 in base 10 ?
In base 10, if there is a fraction \dfrac{p}{q} satisfying q = 2^m5^n, (m, \ n) \in \mathbb{W} then the fraction is terminating. Do you know this?
Ok, then now , how this , solves the problem?
I had the idea of converting it to base 10 and using this property.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
while (n--) {
long long p, q, b;
cin >> p >> q >> b;
long long g = gcd(p, q);
q /= g;
b = gcd(q, b);
while (b != 1) {
while (q % b == 0) q /= b;
b = gcd(q, b);
}
if (q == 1)
cout << "Finite\n";
else
cout << "Infinite\n";
}
return 0;
}
I don’t know what this solution really wanna do.
It does exactly what the editorial says (which I didn’t understand).
1 Like
p/q can be represented in base b, if p/q \times b^x is an integer for some finite x. This is because multiplying by b moves the decimal one point to the right. If there are finite digits to the right of the decimal point, then eventually it will become an integer, as there would be no more digits to the right of the decimal point.
1 Like
ok , but explain me , how this can solves the above problem ?
We need q to divide b^x. Now that is possible only if there is no prime k such that k divides q and not b.
If there exists a prime k that does not divide b, but divides q, no matter how much I divide by \gcd(b,q), q will never become 1. If there does not exist any k then the \gcd(b,q) will become 1 only when q=1.
Now we can start with a simple algorithm
q/=__gcd(p,q);
while(__gcd(b,q)!=1){
q/=__gcd(b,q);
}
This will TLE as it is O(\log^2 q). We can optimise it by changing it to this.
q/=__gcd(p,q);
while(__gcd(b,q)!=1){
ll x =__gcd(b,q);
while(q%x == 0){
q/=x;
}
}
It is optimised because the inner loop will execute at most s times in total, where s is the largest power of any prime in the prime factorisation of q, which is O(\log q) and the gcd will be calculated at most 6 \times 2 times. The 2 is because it’s calculated twice each time. See if you can find out why.
Hint
It takes 6 iterations on
q = 13 \times 11^2 \times 7^3 \times 5^4 \times 3^5 \times 2^6 and b = 13\times 11 \times 7 \times 5 \times 3 \times 2
3 Likes
We Know that in b th base numeral , to write something whose decimal value is lesser than 1, we use negative power weights from left to write after the decimal point.
For ex->If in the b base numeral if i write 0.123, then its
decimal equivalent will be evaluated by 1 X pow(b,-1)+2 x pow(b,-2)+3 x pow(b,-3).
So, if we have the fraction p/q, where p and q have no factors in common, and if it has finite number of digits after the decimal points ,then it can be written as
p/q= a1/pow(b,i1)+a2/pow(b,i2)+…an/pow(b,in);
where i1<i2<…<in.
,
(p/q)pow(b,in)=a1pow(b,in-i1)+a2*pow(b,in-i2)+…an.
From,here you can clearly observe that the RHS is an integer,so LHS too needs to be an integer which is possible only when q is a factor of pow(b,in) for some
in>0. This is feasible only if all the prime factors of q are also the prime factors of b!
Please, reply if you don’t understand anything!
1 Like
Thanks @everule1 @akhacker579 finally I understand thanks a lot .