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 ;
}
【问题描述】
有N个数，随机选择一段区间，如果这段区间的所有数的平均值在[
最新文章
热门文章