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

Problem Description

在学习完各类算法之后，yuna决定开始学习数论了。yuna神当然从最简单的最小公倍数学起喽~~~~~
定义 为1，2，…，n的最小公倍数，例如，B₁ = 1，B₂ = 2，B₃ = 6，B₄ = 12，B₅ = 60，……。
yuna想知道对于给出的任意整数n，B_n是否等于B_n-1。yuna当然是知道答案的喽，但是她想考考rexdf,这次rexdf囧了，请帮帮他吧！

Input

本题有多组测试数据，输入的第一行是一个整数T代表着测试数据的数量，接下来是T组测试数据。
对于每组测试数据：包含一个整数n (2 ≤ n ≤ 10¹⁶)。

Output

对于每组测试数据：
第1行 如果B_n等于B_n-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则相等，反之不相等。

#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;
}