欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2020 CCPC Wannafly Winter Camp Day1 H 最大公约数(唯一分解定理)

程序员文章站 2022-07-15 16:10:41
...

题目链接
2020 CCPC Wannafly Winter Camp Day1 H 最大公约数(唯一分解定理)
思路:题意就是说在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);
        }
    }
 
}