哈理工oj 1328相等的最小公倍数解题报告

链接：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1328

这道题是说，前n个正整数即1,2,3......n所有数的最小公倍数定义为An,例如A1=1,A2=2,A3=6......

这道题是说，如果给定一个数n是否满足An=A(n-1)；

我们首先进行一下分析，首先，如果n是素数，那么很明显An!=An-1,剩余的问题就是，如果n是合数的时候，该如何判断，首先呢，我么可以看到，我么可以得出结论，如果An!=An-1那么，n一定不存在互素的因子对。我们可以进行以下证明，我们知道LCM(a,b)=a*b/gcd(a,b),也就是说，如果gcd(a,b)>=2即两个数不互素的话，那么这两个数所确定的最小公倍数一定<a*b=n，也就不能被n整除，既然不能被n整除，又怎么是他的倍数呢，所以，一个数如果满足an=an-1，必须保证，存在因子对满足gcd(a,b)=1那么我们只要找n所有的成对的因子有没有满足这种情况的就可以了，标程上说是n不为任何素数的幂的时候，就可以保证an=an-1，其实仔细想想和我的推论是一样的

View Code

 1 #include<stdio.h>
 2 #include<math.h>
 3 #include<string.h>
 4 int gcd(int a,int b)
 5 {
 6     if(a%b==0)
 7     return b;
 8     return gcd(b,a%b);
 9 }
10 int main()
11 {
12     int n;
13     int t;
14     int i,j;
15     scanf("%d",&t);
16     while(t--)
17     {
18         bool p=true;
19         scanf("%d",&n);
20         if(n==2)
21         {
22             printf("NO\n");
23             continue;
24         }
25         int temp=(int)sqrt((double)n);
26         for(i=2;i<=temp;i++)
27         {
28             if(n%i==0)
29             break;
30         }
31         if(i==temp+1)
32         {
33             printf("NO\n");
34             continue;
35         }
36         for(i=2;i<=temp;i++)
37         {
38             if(n%i==0)
39             {
40                 int q=n/i;
41                 if(gcd(q,i)==1)
42                 {
43                     p=false;
44                     break;
45                 }
46             }
47         }
48         if(p)
49         printf("NO\n");
50         else
51         printf("YES\n");
52     }
53     return 0;
54 }