【问题描述】
从1− ?中找一些数乘起来使得答案是一个完全平方数，求这个完全平方数
最大可能是多少。
【输入格式】
第一行一个数字?。
【输出格式】
一行一个整数代表答案对100000007取模之后的答案。
【样例输入】
7
【样例输出】
144
【样例解释】
但是塔外面有东西。
【数据规模与约定】
210。
55000。
70%的数据，1 ≤ ? ≤ 10 5 。
对于100%的数据，1 ≤ ? ≤ 5× 10 6 。
思路：
打素数表+分解质因数=满分ac-->ak虐场-->noip一等-->noi金牌-->IOI金牌-->acm领奖台(别做梦了写代码吧)
来，上代码：
#include<cstdio> #define LL long long
#define INF 100000007LL using namespace std; LL n,Num(),Ans=,Sum[]={},Prime[];
bool Flag[]={}; LL Count(LL S,LL X)
{
LL Number=;
while (S)
{
if (S&)
Number=(Number*X)%INF;
X=(X*X)%INF;
S>>=;
}
return Number;
} void Euler()
{
for (LL a=;a<=n;a++)
{
if (!Flag[a])
Prime[Num++]=a;
for (LL b=;b<Num&&a*Prime[b]<=n;b++)
{
Flag[a*Prime[b]]=true;
if (!(a%Prime[b]))
break;
}
}
} int main()
{
scanf("%I64d",&n);
Euler();
for (LL a=;a<Num;a++)
{
LL t=n;
while (t)
{
Sum[a]+=t/Prime[a];
t/=Prime[a];
}
}
for (LL a=;a<Num;a++)
if (Sum[a]&)
Ans=(Ans*Count(Sum[a]-,Prime[a]))%INF;
else
Ans=(Ans*Count(Sum[a],Prime[a]))%INF;
printf("%I64d",Ans);
return ;
}