思路

• 关键结论：将分数约分为 $p'/q'$，其中 $q' = q / \gcd(p,q)$。分数在 $k$ 进制下为有限小数，当且仅当 $q'$ 的所有质因子都来自 $k$。等价地，存在某个正整数 $t$ 使

• 等价算法：反复用 $\gcd(q', k)$ 去除 $q'$ 中与 $k$ 的公共质因子，直到 $\gcd(q', k) = 1$。若最终得到 $q' = 1$，则为有限小数，否则不是。

• 步骤：

  • 计算 $g=\gcd(p,q)$，令 $q' = q / g$。
  • 循环计算 $g=\gcd(q',k)$，当 $g>1$ 时令 $q' \gets q'/g$，直至 $g=1$。
  • 若此时 $q'=1$，输出 yes，否则 no。

• 复杂度：每次循环至少去掉一个质因子，多至约 $\mathcal{O}(\log q)$ 次；整体对每组数据为对数级，适用于 $T$ 高达 $10^5$。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	if (!(cin >> T)) return 0;
	while (T--) {
		unsigned long long p, q, k;
		cin >> p >> q >> k;
		// 约分：q' = q / gcd(p, q)
		unsigned long long g = std::gcd(p, q);
		unsigned long long qp = q / g;

		// 反复去除与 k 的公共质因子
		while (qp > 1) {
			unsigned long long gg = std::gcd(qp, k);
			if (gg == 1) break;
			qp /= gg;
		}

		cout << (qp == 1 ? "yes" : "no") << '\n';
	}
	return 0;
}

Python

import sys
import math

def is_terminating(p: int, q: int, k: int) -> bool:
    # 约分 q' = q / gcd(p, q)
    g = math.gcd(p, q)
    qp = q // g
    # 反复去除与 k 的公共质因子
    while qp > 1:
        gg = math.gcd(qp, k)
        if gg == 1:
            break
        qp //= gg
    return qp == 1

def main():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    T = int(next(it))
    out_lines = []
    for _ in range(T):
        p = int(next(it)); q = int(next(it)); k = int(next(it))
        out_lines.append("yes" if is_terminating(p, q, k) else "no")
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
	static class FastScanner {
		private final InputStream in;
		private final byte[] buffer = new byte[1 << 16];
		private int ptr = 0, len = 0;
		FastScanner(InputStream is) { in = is; }
		private int read() throws IOException {
			if (ptr >= len) {
				len = in.read(buffer);
				ptr = 0;
				if (len <= 0) return -1;
			}
			return buffer[ptr++];
		}
		long nextLong() throws IOException {
			int c; do { c = read(); } while (c <= 32);
			int sign = 1;
			if (c == '-') { sign = -1; c = read(); }
			long val = 0;
			while (c > 32) {
				val = val * 10 + (c - '0');
				c = read();
			}
			return val * sign;
		}
		int nextInt() throws IOException { return (int) nextLong(); }
	}

	static long gcd(long a, long b) {
		while (b != 0) {
			long t = a % b;
			a = b;
			b = t;
		}
		return a >= 0 ? a : -a;
	}

	public static void main(String[] args) throws Exception {
		FastScanner fs = new FastScanner(System.in);
		StringBuilder sb = new StringBuilder();
		int T = (int) fs.nextLong();
		for (int t = 0; t < T; t++) {
			long p = fs.nextLong();
			long q = fs.nextLong();
			long k = fs.nextLong();

			// 约分 q' = q / gcd(p, q)
			long g = gcd(p, q);
			long qp = q / g;

			// 反复用 gcd 去除与 k 的公共质因子
			while (qp > 1) {
				long gg = gcd(qp, k);
				if (gg == 1) break;
				qp /= gg;
			}
			sb.append(qp == 1 ? "yes" : "no").append('\n');
		}
		System.out.print(sb.toString());
	}
}

题目内容

小美是一位数学爱好者，她想知道给定的有理数 $\frac{p}{q}$ 在 $k$ 进制下是否为一个有限小数。

换句话说，她希望判断在基数为 $k$ 的表示中，该分数的小数部分是否会在有限位后结束，而不是无限循环。

例如，$\frac{1}{2}$ 在十进制下装示为 $0.5$ ，是有限小数；相比之下，$\frac{1}{3}$ 在十进制下表示为 $0.3$ ，不是有限小数。

输入描述

第一行输入一个整数 $T(1≤T≤10^5)$ ，表示测试数据的组数。

接下来 $T$ 行，每行输入三个整数 $p,q,k(1≤p,q≤10^{18},2≤k≤10^{18})$，分别表示分子 $p$、分母 $q$ 和进制基数。

输出描述

对于每一组测试数据，输出一行结果，若 $\frac{p}{q}$ 在 $k$ 进制下是 有限小数，则输出 $yes$ ；否则输出 $no$ 。

样例1

输入

3
1 2 10
1 3 10
5 4 2

输出

yes
no
yes

说明

• $\frac{1}{2}$在十进制下为 $0.5$ ，是有限小数，因此输出 $yes$ ；

• $\frac{1}{3}$在十进制下为 $0.3$，是无限循环小数，因此输出 $no$；

• $\frac{3}{4}$在二进制下为 $0.11_2$，是有限小数，因此输出 $yes$ 。