本文共 1058 字，大约阅读时间需要 3 分钟。

【题目】

【题解】

对于给定的范围[1,n]内的k，要求我们判断是否正确，并输出最小的判断数字。

首先我们根据样例来递推一下思路是否正确：

Input ：10 1    Output：210

假如k是正确的，那么gcd(k,k)=k；所以假如不正确，我们只需要考虑i在[1,n]范围内gcd(i,k)==k的数字。

对于1来说，有2,3,4,5,6,7,8,9,10这几个数字gcd为1  即为：2,3,2^2,5,2*3,7,2^3,3^2.

因为要求数字最小，所以我们把不必要的数字除去，直到处理完所有可能数字：

1. 1*2，2,3,2^2,5,2*3,7,2^3,3^2
2. 1*2*3，2,3,2^2,5,2*3,7,2^3,3^2
3. 1*2*3*5，2,3,2^2,5,2*3,7,2^3,3^2
4. 1*2*3*5*7，2,3,2^2,5,2*3,7,2^3,3^2
5. 综上所述，答案为1*2*3*5*7=210.

根据这个，可以推一下20 3的答案为3*2*3*5=90.

然后我们考虑极限值，最大的情况是500 1，即需要把500以内所有素数相乘，答案太大存不下，所以需要用到大数乘法。

因此我用java写了。

【代码】

import java.util.*;import java.math.*;public class Main{    public static void main(String args[]){       Scanner cin = new Scanner(System.in);       int [] a= new int[510];       int T=cin.nextInt();       for(int _=1;_<=T;_++) {    	   int n=cin.nextInt();    	   int k=cin.nextInt();    	   BigInteger ans=BigInteger.valueOf(k);    	   for(int i=k+k;i<=n;i+=k) {    		   if(a[i]==_) continue;    		   ans=ans.multiply(BigInteger.valueOf(i/k));    		   for(int j=i+i;j<=n;j+=i)    			   a[j]=_;    	   }    	   System.out.println(ans);       }    }}

转载地址：http://yefen.baihongyu.com/