http://codeforces.com/contest/984/problem/C
C. Finite or not
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
题目标签:数论;
题目大意:判断p/q在b进制下是否为有限小数;
0.0
题目思路:不断的用b去消除q中的因子,但是求出一个g=gcd(q,b)后,必须直接将q中的所有g都除尽,否则会超时;标程是不断的寻找b=gcd(q,b),因为每次q除尽最大公约数后,q中含有的只能是原来的最大公约数中的因子,所以不用每次用b去更新q,可以每次更新完q后,也更新b值;
小数的二进制转换:乘基取整,顺序排列;
#include <iostream>
#include <cstdio>
//小数的二进制转换:乘基取整,顺序排列;
//b的k次方%q==0;
//判断k个b能否将q的所有因子均消耗完;
using namespace std;
typedef long long ll; ll gcd(ll x,ll y)
{
if(y==)return x;
return gcd(y,x%y);
}
int main()
{
int n;
ll p,q,b;
scanf("%d",&n);
while(n--)
{
bool flag=false;
scanf("%I64d%I64d%I64d",&p,&q,&b);
if(p==)q=;
q/=gcd(p,q);
ll g=gcd(q,b);
while(g!=){ //q,b互质;
while(q%g==)q/=g;
g=gcd(q,b);
}
if(q==)
printf("Finite\n");
else
printf("Infinite\n");
}
return ;
}