一个$b$进制最简分数是有限循环小数当且仅当其分母没有与$b$不同的质因子，小学数奥内容水过
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 long long T,n,m,b,g; 6 long long gcd(long long a,long long b) 7 { 8 return b?gcd(b,a%b):a; 9 } 10 int main () 11 { 12 scanf("%lld",&T); 13 while(T--) 14 { 15 scanf("%lld%lld%lld",&n,&m,&b); 16 if(!(n%m)) {printf("Finite "); continue ;} 17 g=gcd(n,m),m/=g; 18 while(m>1) 19 { 20 g=gcd(b,m); 21 if(g==1) break; 22 while(!(m%g)) m/=g; 23 } 24 m>1?printf("Infinite "):printf("Finite "); 25 } 26 return 0; 27 }