P8754 [蓝桥杯 2021 省 AB2] 完全平方数

· · 个人记录

这个题太简单了以至于没有题解，那我来水一篇。

题意

题意很简单，就是给定一个n，求一个x，使得n*x是某个数的平方。

解题思路

30分思路

从1开始枚举x，然后判断n*x是不是平方数，如果是平方数，输出x，时间复杂度为O(n)

代码略

100分思路

假设n*x是平方数，如果存在b，c，使得x=b * b * c，则可以证明n * c也是平方数，所以要x最小，x中一定不能再拆出平方数（或者x=1）。那么，如果n * x是平方数,则n*x可以分解为a_1^2 * a_2^2 * … * a_i^2 * x^2, 也就是说 n 可以拆分成 a_1^2 * a_2^2 * … * a_i^2 * x。

那已知n，如何寻找x呢？从上面可以看出来，只要把n中所有的平方数全部除掉，就可以得到x。也就是，从2开始枚举i，如果 i * i是n的因数，就令n=n/(i * i)。最后，n中不再有平方数时，此时的n就是x。时间复杂度O（\sqrt{n}）

#include<bits/stdc++.h>
using namespace std;
long long a,n;
int main()
{
    scanf("%lld",&n);
    for(long long i=2;i*i<=n;i++)
    {
        while(n%(i*i)==0)n/=(i*i);
    }
    printf("%lld",n);
}

注意，循环中的i一定要是long long 类型的，因为过程中存在i * i，如果i是int类型，那么i * i也就默认为int类型，而i可能为10^6,i * i会超过int的范围，从而导致错误。