游客 注册 | 登录
中文 | En

3053 - 最大完全平方因子

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

Q学长是一个完全平方数控，有一天他想到了一个有趣的问题，给你一个数N，求它的因子数中，是完全平方数的最大的那个数是多少，怎么样这个问题很简单吧，所以请各位帮Q学长解决一下。

题目输入

输入数据有多组，输入一个数N（1<=N<=10^18）

题目输出

对于每组数据N，输出N的因子中是完全平方数的最大的那个数。

输入/输出样例

输入格式

72

输出格式

36

C++解答

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const long long maxn=1000005;
const long long N=96000;
long long cnt;
long long n;
bool is_prime[maxn];
long long prime[maxn];
long long a[N];

void dabiao()
{
    is_prime[0]=is_prime[1]=1;
    long long  i;
    for(i=2;i<=maxn;i++)
    {
        is_prime[i]=0;
    }
    for(i=2;i<=maxn;i++)
    {
        if(is_prime[i]!=0)
        {
            continue;
        }
        for(long long  j=2*i;j<=maxn;j+=i)
        {
            is_prime[j]=1;
        }
    }
    cnt=0;
    for(long long i=2;i<=maxn;i++)
    {
        if(is_prime[i]==0)
        {
            prime[cnt++]=i;
        }
    }
}
int main()
{
   // freopen( "D.txt", "r", stdin );
   // freopen( "_D.txt", "w", stdout );
    dabiao();
    while(cin>>n)
    {
        long long res=1,tmp=0;
        for(long long i=0;i<cnt&&prime[i]<=n;i++)
        {
            if(n%prime[i]==0)
            {
                tmp=0;
                while(n%prime[i]==0)
                {
                    n/=prime[i];
                    tmp++;


                }
                if(tmp&1) tmp--;
                for(int j=0;j<tmp;j++) res*=prime[i];
            }
        }
        if(n!=1)
        {
            long long x=(long long )(sqrt(n+0.0));
            if(x*x==n)
            {
                res*=n;
            }
        }
        cout<<res<<endl;
    }
    return 0;
}
请先登陆