【问题描述】

从1− ?中找一些数乘起来使得答案是一个完全平方数，求这个完全平方数

最大可能是多少。

【输入格式】

第一行一个数字?。

【输出格式】

一行一个整数代表答案对100000007取模之后的答案。

【样例输入】

7

【样例输出】

144

【样例解释】

但是塔外面有东西。

【数据规模与约定】

210。

55000。

70%的数据，1 ≤ ? ≤ 10 5 。

对于100%的数据，1 ≤ ? ≤ 5× 10 6 。

 

思路：

　　打素数表+分解质因数=满分ac-->ak虐场-->noip一等-->noi金牌-->IOI金牌-->acm领奖台(别做梦了写代码吧)

　　　　来，上代码：

#include
     
      #define LL long long#define INF 100000007LLusing namespace std;LL n,Num(0),Ans=1,Sum[350000]={
   0},Prime[350000];bool Flag[5000001]={
   0};LL Count(LL S,LL X){    LL Number=1;    while (S)    {        if (S&1)          Number=(Number*X)%INF;        X=(X*X)%INF;        S>>=1;    }    return Number;}void Euler(){    for (LL a=2;a<=n;a++)    {        if (!Flag[a])        Prime[Num++]=a;        for (LL b=0;b
      
       <=n;b++)        {            Flag[a*Prime[b]]=true;            if (!(a%Prime[b]))              break;        }    }}int main(){    scanf("%I64d",&n);    Euler();    for (LL a=0;a