首页 > 代码库 > 清北第三套题
清北第三套题
【问题描述】
从中找一些数乘起来使得答案是一个完全平方数，求这个完全平方数最大可能是多少。
【输入格式】
第一行一个数字。
【输出格式】
一行一个整数代表答案对取模之后的答案。
【样例输入】
7
【样例输出】
144
【样例解释】
但是塔外面有东西。
【数据规模与约定】
对于20%的数据，1<=N<=100。
对于50%的数据，1<=N<=5000。
对于70%的数据，1<=N<=10^5。
对于100%的数据，1<=N<=5*10^6。
题解：可以将n的阶乘质因数分解，然后若质因数的指数为奇数则指数减1乘进答案。若为偶数直接乘进答案。因为只有当质因数的指数是偶数时，才能开方开出来，当质因数指数是奇数时，可以除以一个这个质因数，就可以开出来了。
#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#define N 5000100using namespace std;const int M=100000007;int n,num(0);long long ans(1);int ss[N],zs[N]={0};bool f[N]={0};int oula()//欧拉筛法 { for (int i=2;i<=n;i++) { if (!f[i]) ss[++num]=i; for (int j=1;j<=num,ss[j]*i<=n;j++) { f[ss[j]*i]=1; if (!(i%ss[j])) break; } }}long long jc(long long p,long long k)//快速幂 { long long ki=1; while (k) { if (k%2) ki=ki*p%M; p=p*p%M; k/=2; } return ki;}int main(){ freopen("hao.in","r",stdin); freopen("hao.out","w",stdout); scanf("%d",&n); oula(); for (int i=1;i<=num;i++)//n的阶乘质因数分解 { int k=n; while (k) { zs[i]+=k/ss[i]; k/=ss[i]; } } for (int i=1;i<=num;i++) { if (zs[i]%2) ans=ans*jc(ss[i],zs[i]-1)%M; else ans=ans*jc(ss[i],zs[i])%M; } cout<<ans<<endl; fclose(stdin); fclose(stdout); return 0;}
清北第三套题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。