2020 CCPC Wannafly Winter Camp Day1 H 最大公约数(唯一分解定理)
程序员文章站
2022-07-15 16:10:41
...
题目链接
思路:题意就是说在1-n范围内,只有唯一一个k的gcd(k,y)=k,很明显,答案肯定k的倍数,因此根据唯一分解定理,我们只需枚举k的倍数(1-n/k),如果倍数是质数的情况下,就*ans,否则的话gcd就会变成1。坑点:注意一下要用大数,不会python,果断Java。
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner cin=new Scanner(System.in);
int T=cin.nextInt();
while(T-->0)
{
int n=cin.nextInt(),k=cin.nextInt();
n/=k;
BigInteger t=BigInteger.valueOf(k);
for(int i=2;i<=n;++i)
{
int flag=0;
for(int j=2;j*j<=i;++j)
if(i%j==0) {flag=1;break;}
if(flag==0) t=t.multiply(BigInteger.valueOf(i));
}
System.out.println(t);
}
}
}