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 这题是与数相关
首先你先要静下心来弄明白这几件事情：
第一：
gcd函数，这个是求最大公约数的函数。
第二：
在小数点后面将十进制转化为二进制，是对十进制*2取一个数，一直*2直到出现1；
例如：0.125（10）转化成二进制是0.001；
这题求1/q转化成其他进制，判断是否为一个有限小数。即1/q *b*b*b...是否==1或者大于一的整数。
注意：不能用cin输入会超时！
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll; ll gcd(ll a,ll b)//求a和b的最大公约数的函数
{
if(!b) return a;
return gcd(b,a%b);
} int main()
{
int n;
scanf("%d",&n);
while(n--)
{
ll p,q,b;
scanf("%I64d %I64d %I64d",&p,&q,&b);
ll g=gcd(p,q);
p=p%q;
p/=g;
q/=g;
if(q==1||p==0)
{
printf("Finite\n");
continue;
}
while(b!=1&&q!=1)
{
b=gcd(q,b);
q/=b;
}
if(q==1) printf("Finite\n");
else printf("Infinite\n");
}
return 0;
}