Codeforces Round #483 (Div. 2) C. Finite or not?(数论,GCD)

时间:2021-05-24 05:15:07
C. Finite or not?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given several queries. Each query consists of three integers ppqq 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.

Input

The first line contains a single integer nn (1n1051≤n≤105) — the number of queries.

Next nn lines contain queries, one per line. Each line contains three integers ppqq, and bb (0p10180≤p≤10181q10181≤q≤10182b10182≤b≤1018). All numbers are given in notation with base 1010.

Output

For each question, in a separate line, print Finite if the fraction is finite and Infinite otherwise.

Examples
input
Copy
2
6 12 10
4 3 10
output
Copy
Finite
Infinite
input
Copy
4
1 1 2
9 36 2
4 12 3
3 5 4
output
Copy
Finite
Finite
Finite
Infinite
Note

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

题意:给出p,q,b,询问在b进制下,p/q是否为无限小数。

题解:首先想到的是在十进制下p/q何时为无限小数,发现当分式最简的时候,分母的因子只存在10的质因子时,一定不是无限小数,反之则是无限小数,则推广到b,将q中所有b的因子除掉,看是否可以将q完全除掉即可。

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<vector>
#include<stdlib.h>
#include<math.h>
#include<queue>
#include<deque>
#include<ctype.h>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<algorithm>
#define gcd(a,b) __gcd(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define FAST_IO ios::sync_with_stdio(false)
#define mem(a,b) memset(a,b,sizeof(a))
const double PI = acos(-1.0);
const double eps = 1e-6;
const int MAX=1e5+10;
const long long INF=0x7FFFFFFFFFFFFFFFLL;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
typedef long long ll;
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ll p,q,b;
        scanf("%I64d %I64d %I64d",&p,&q,&b);
        ll GCD=b;
        q/=gcd(p,q);

        while(q!=1)
        {
            GCD=gcd(GCD,q);
            if(GCD==1) break;
            q/=GCD;
        }

        if(q==1) printf("Finite\n");
        else printf("Infinite\n");
    }
    return 0;
}