数论 A. yuna学数论 判断1到n连续n个数的最小公倍数与1到n-1连续n-1个数的最小公倍数是否相等

Problem Description

在学习完各类算法之后，yuna决定开始学习数论了。yuna神当然从最简单的最小公倍数学起喽~~~~~
定义 为1，2，…，n的最小公倍数，例如，B1 = 1，B2 = 2，B3 = 6，B4 = 12，B5 = 60，……。
yuna想知道对于给出的任意整数n，Bn是否等于Bn-1。yuna当然是知道答案的喽，但是她想考考rexdf,这次rexdf囧了，请帮帮他吧！
Input
本题有多组测试数据，输入的第一行是一个整数T代表着测试数据的数量，接下来是T组测试数据。
对于每组测试数据：包含一个整数n (2 ≤ n ≤ 1016)。
Output
对于每组测试数据：
第1行 如果Bn等于Bn-1则输出YES否则输出NO。
Sample Input

1
6

Sample Output

YES

Author
Kuangbin
Source
developing schools contest 5

思路：
首先先得知道，每一个数都可以写成一个或多个素数的乘积，例如
1=1    2=2    3=3   
4=2*2    5=5    6=2*3    7=7
8=2*2*2    9=3*3  10=2*5   11=11

通过观察可以发现前n位数的最小公倍数

的公式。

例如前4位数的最小公倍数ans[4]=1*2*3*2=12.  怎么来的呢？

是前四项的因数相乘得到。其中factor[1](因数1)=1  factor[2]=2  factor[3]=3   factor[4]=2，为什么第四位的因数为2,？这是因为前面已经有

一个2，相当于抵消掉一个2（可以这么理解）  即factor[5]=5  factor[6]=1（抵消factor[2]与factor[3]）   factor[9]=3（抵消factor[3]）

所以前n为的最小公倍数即前n项因子之积。

所以前n位的最小公倍数如果等于前n-1位的最小公倍数那么第n位一定不是素数，并且因式分解的因子都在之前出现过。即对n的两个因子（n/i,i）求最大公约数，如果是1则相等，反之不相等。

[cpp] view plain copy

    #include <iostream>  
    #include <string>  
    #include <cstdio>  
    using namespace std;  
    #define LL long long  
    LL gcd( LL a,LL b)  
    {  
     return b==0?a:gcd(b,a%b);  
    }  
    int main()  
    {//1.判断1到n连续n个数的最小公倍数与1到n-1连续n-1个数的最小公倍数是否相等  
        LL n;  
        scanf("%lld",&n);  
        int flag=1;  
        for(LL i=2; i*i<=n; i++)  
           if(n%i==0)  
            {  
                LL tt=gcd((n/i),i);  
                if(tt-1==0)  
                {  
                    flag=0;  
                    printf("YES\n");  
                    break;  
                }  
            }  
        if(flag) printf("NO\n");  
        return 0;  
    }