题目传送门
题目描述
有三个人， A , B , C A,B,C A,B,C，其中 A A A 和 B B B 共享了一个神秘的数字 k k k，已知 1 ≤ k ≤ n 1 \leq k \leq n 1≤k≤n 。
现在 A A A 和 C C C 说：“ k k k 的值等于 x x x”。
C C C 不太信任 A A A，于是想向 B B B 确认一下 k k k 是否真的等于 x x x。 B B B 虽然不想直接把 k k k 的值告诉 C C C，但是 B B B 允许 C C C 给出一个正整数 y y y（注意 y y y 可以大于 n n n），然后 B B B 会回答 gcd ? ( k , y ) \gcd(k,y) gcd(k,y) 。
现在给出 k , n k,n k,n，你需要帮助 C C C 决定这样的 y y y 的取值，使得 C C C 一定可以通过 B B B 的回答来判断 A A A 有没有撒谎。如果这样的 y y y 有多个，你需要输出最小的那个。
输入描述:
输入第一行是一个整数 T ( 1 ≤ T ≤ 50 ) T(1 \leq T \leq 50) T(1≤T≤50)。
对于每组数据，输入一行两个整数 n , k ( 1 ≤ k ≤ n ≤ 500 ) n,k(1 \leq k \leq n \leq 500) n,k(1≤k≤n≤500)。
输出描述:
对于每组数据，输出一行一个整数，表示答案。如果满足条件的 y y y 不存在，则输出 ? 1 -1 ?1。
输入
3
10 1
10 4
10 7
输出
210
8
7
题解
- 考虑 yy 的取值：
- y y y 必须是 k k k 的倍数，否则无法区分 g c d ( y , k ) gcd(y,k) gcd(y,k) 和 k k k 。
- 对于 [ 1 , ? n k ? ] \left[1,\left\lfloor\frac{n}{k}\right\rfloor\right] [1,?kn??] 的每一个质数 p p p， y k \frac{y}{k} ky? 必须是 p p p 的倍数，否则无法区分 k k k 和 p k pk pk。
- 因此设 p 1 , … , p m p_1,\dots ,p_m p1?,…,pm? 为 [ 1 , ? n k ? ] \left[1,\left\lfloor\frac{n}{k}\right\rfloor\right] [1,?kn??] 中的所有质数，那么答案就是 k k k ∏ i = 1 m p i \prod_{i=1}^{m} p_{i} ∏i=1m?pi? 。用高精度计算后就能得到答案。
AC-Code
import java.math.BigInteger;
import java.util.Scanner;public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);int T = cin.nextInt();while(T-- > 0) {
int n = cin.nextInt(), k = cin.nextInt();BigInteger t = BigInteger.valueOf(k);for(int i = 2; i <= n / k; ++i) {
Boolean f = true;for(int j = 2; j * j <= i; ++j) {
if(i % j == 0) f = false;}if(f) t = t.multiply(BigInteger.valueOf(i));}System.out.println(t);}}
}