10.30 morning

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

P75
竞赛时间： ???? 年 ?? 月 ?? 日 ??:??-??:??

注意事项（请务必仔细阅读）

【问题描述】

从1 − N中找一些数乘起来使得答案是一个完全平方数，求这个完全平方数
最大可能是多少。
【输入格式】
第一行一个数字N。
【输出格式】
一行一个整数代表答案对100000007取模之后的答案。
【样例输入】
7
【样例输出】
144
【样例解释】
但是塔外面有东西。
【数据规模与约定】
对于20%的数据， 1 ≤ N ≤ 100。
对于50%的数据， 1 ≤ N ≤ 5000。
对于70%的数据， 1 ≤ N ≤ 105。
对于100%的数据， 1 ≤ N ≤ 5 × 106。

/*数论题 筛素数的时候是到maxn不是n 然后就有了第一天6.2s的梗2333*/

#include<iostream>

#include<cstdio>

#define maxn 5000010

#define mod 100000007

#define ll long long

using namespace std;

ll n,prime[maxn/],c[maxn/],num,ans=;

bool f[maxn];

void Prime(){

    for(int i=;i<=maxn-;i++){//下次筛到n....

        if(f[i]==)prime[++num]=i;

        for(int j=;j<=num;j++){

            if(i*prime[j]>maxn-)break;

            f[i*prime[j]]=;

            if(i%prime[j]==)break;

        }

    }

}

void Solve(){

    for(int i=;i<=num;i++){

        ll P=prime[i];

        if(P>n)break;

        while(n>=P){

            c[i]+=n/P;P*=prime[i];

        }

    }

}

ll Qc(ll a,ll b){

    ll r=;

    while(b){

        if(b&)r=r*a%mod;

        b>>=;a=a*a%mod;

    }

    return r%mod;

}

int main()

{

    freopen("hao.in","r",stdin);

    freopen("hao.out","w",stdout);

    cin>>n;

    Prime();Solve();

    for(int i=;i<=num;i++)

        if(c[i]&)c[i]--;

    for(int i=;i<=num;i++){

        if(prime[i]>n)break;

        ans=ans*Qc(prime[i],c[i])%mod;

    }

    cout<<ans<<endl;

    return ;

}