【NOIP模拟赛】【数学】完全平方数

问题描述

一个数如果是另一个整数的完全平方，那么我们就称这个数为完全平方数（Pefect Sqaure），也称平方数。

小A认为所有的平方数都是很perfect的~

于是他给了小B一个任务：用任意个不大于n的不同的正整数相乘得到完全平方数，并且小A希望这个平方数越大越好。

请你帮助小B告诉小A满足题意的最大的完全平方数。

输入

输入文件名为number.in

输入仅 1行，一个数n。

输出

输出文件名为number.out

输出仅1行，一个数表示答案。由于答案可以很大，所以请输出答案对100000007(注意！10^8+7)取模后的结果。

输入输出样例1

number.in

number.out

144

输入输出样例解释1

144=2×3×4×6，是12的完全平方。

输入输出样例2

number.in

number.out

5184

输入输出样例解释2

5184=3×4×6×8×9，是72的完全平方。

数据范围

对于20%的数据，0<n≤100；

对于50%的数据，0<n≤5,000；

对于70%的数据，0<n≤100,000；

对于100%的数据，0<n≤5,000,000。

题解

这题可以简化为在[1,n]中取任意个数，组成最大的形如ans=a^(2*Na)*b^(2*Nb)*……的数即可

很容易发现大于n/2+1的数和质数都不能选择作为底数

而在剩下的数中我们可以枚举i，在[1,n]数字中将每个数字分解为i^xi*φ的形式，记录下Σxi

易证Σxi只有为偶数时才能组成完全平方，取i^(Σxi)，

当Σxi为奇数时我们取i^(Σxi-1)

所以答案就为Σ(i^(Σxi-1))

 #include<iostream>

 #include<cstdlib>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 long long n,ans;

 bool zs[];

 long long query(long long);

 long long work(long long,long long);

 int main()

 {

     long long i,j,sum;

     scanf("%I64d",&n);

     for(i=;i<=n/+;i++)

       if(!zs[i]) for(j=;i*j<=n;i++) zs[i*j]=true;

     ans=;

     for(i=;i<=n/+;i++)

     {

         if(!zs[i])

         {

             cout<<"*"<<i<<endl;

             j=;

             sum=query(i); cout<<sum<<endl;

             if(sum%!=) sum--;

             if(sum!=) j=work(i,sum); cout<<j<<endl;

             if(j!=) ans=(ans*j)%;

         }

     }

     printf("%I64d",ans);

     return ;

 }

 long long query(long long v)

 {

     long long ans,x;

     ans=;

     x=n;

     for(;x>;x/=v,ans+=x);

     return ans;

 }

 long long work(long long a,long long b)

 {

     long long ans=,x=a%;

     for(;b>;b/=,x=(x*x)%) if(b%!=) ans=(ans*x)%;

     return ans;

 }

巴特西

【NOIP模拟赛】【数学】完全平方数

最新文章

热门文章