题目
给定三个整数 p,q,b，请你计算十进制表示下的 p/q 的结果在 b进制下是否为有限小数。
输入格式
第一行包含整数 TT，表示共有 TT 组测试数据。
每组数据占一行，包含三个整数 p,q,b。
输出格式
每组数据输出一行结果，如果 p/q的结果在 b 进制下是有限小数，则输出 YES，否则输出 NO。
数据范围
前五个测试点满足 1≤T≤101≤T≤10。
所有测试点满足 1≤T≤105，0≤p≤1018，1≤q≤1018，2≤b≤1018。
输入样例1：
输出样例1：
输入样例2：
1
2
3
4
5
| 4
1 1 2
9 36 2
4 12 3
3 5 4
|
输出样例2：
笔者解析
本题为ACwing的周赛困难题。所运用到的主要知识为：
小数进制转换计算
十进制小数→R进制小数
乘R取整顺序法：乘基数取整，连续乘以基数，并取其整数，直到积为零或达到所要求的精度时，将所得整数正序排列即可。
由此题将小数转换为二进制，可看出是小数不断的乘2，取最整数位为结果位，取小数位为下一个继续计算位，直到下一计算位最终取值为0。
约分
本题有两个地方需要约分
初始的p/q，要进行初始约分去除两数之间的公因数。
要拿q与d进行不断约分，每次找到最大公因数g,不断使用q/=d，直到q与d之间的最大公约数为g=1
为什么要这样计算呢?因为我们的q一定要能被d的次方整除，才可以被转换成其它进制的有限小数，使用d的次方，也就需要不断要取得新的q与d的g值。
笔者代码
java版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(bufferedReader.readLine());;
while (n-->0){
int []arr = new int[n];
String []a = bufferedReader.readLine().split(" ");
long p= Long.parseLong(a[0]);
long q= Long.parseLong(a[1]);
long b= Long.parseLong(a[2]);
if(p%q==0||p == 0){System.out.println("YES");continue;}
long y = gcd(p,q);
p/=y;q/=y;
long g ;
while(true){
g = gcd(q,b);
if(g == 1){ break;}
while(q%g==0){ q /= g; }
}
if(q == 1){
System.out.println("YES");
continue;
}else {
System.out.println("NO");
}
}
bufferedReader.close();
}
public static long gcd(long a,long b){
if(a%b == 0){
return b;
}
return gcd(b,a%b);
}
}
|
c++ y总版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
int T;
scanf("%d", &T);
while (T -- )
{
LL p, q, b;
scanf("%lld%lld%lld", &p, &q, &b);
LL d = gcd(p, q);
q /= d;
while (q > 1)
{
d = gcd(q, b);
if (d == 1) break;
while (q % d == 0) q /= d;
}
if (q == 1) puts("YES");
else puts("NO");
}
return 0;
}
作者：yxc
链接：https:
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
|
