Codeforces Round #483 (Div. 2) C.Finite or not? 关于欧几里得的应用

时间:2022-08-08 05:15:22

C. Finite or not?

Input

The first line contains a single integer nn (1n10^) — the number of queries.

Next nn lines contain queries, one per line. Each line contains three integers pq and b (0p10^181q10^18 2b10^18). 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.

input
2
6 12 10
4 3 10
output
Finite
Infinite
Codeforces Round #483 (Div. 2) C.Finite or not? 关于欧几里得的应用

即要求输入,p,q,b.

问:是否有n个p/q能组成b,n必需为有理数,可以是小数,但必需有限。

思路:该问题立刻就想到gcd,主要是与b的关系,应有b与q的gcd关系,进行求解。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef unsigned long long unsll;
 4 
 5 int n;
 6 unsll p,q,b;
 7 unsll gcd(int a,int b)
 8 {
 9     return b==0? a:gcd(b,a%b);
10 }
11 
12 int main()
13 {
14     ios_base::sync_with_stdio(0); cin.tie(0);
15 
16     while( cin >> n ){
17         while(n--){
18             cin >> p >> q >> b;
19             if(p%q==0){
20                 puts("Finite");
21                 continue;
22             }
23 
24             unsll cheek=gcd(p,q);
25             q/=cheek;
26             cheek=gcd(b,q);
27             while(q!=1&&cheek!=1){
28                 while(q%cheek==0) q/=cheek;
29                 cheek=gcd(b,q);
30             }
31             if(q==1)
32                 puts("Finite");
33             else puts("Infinite");
34         }
35     }
36     return 0;
37 }