P8754完全平方数

题目

问题规模:

分析

本题为质因数分解.

本题的证明(不保证正确性,仅仅为个人思考的过程):

题目中N,X均为正整数(为避免冲突使用大写).

则由题意得$\exists 正整数K,使得N*X = K^2$,对3者分解质因数得:

$N = q_1 * q_2 * q_3 * ... * q_n \\ X = p_1 * p_2 * p_3 * ... * p_m \\ K = s_1 * s_2 * s_3 * ... * s_r$

其中$q_i,p_i和s_i$均为素数,则有$K^2 = s^2_{1}*s^2_{2}*s^2_{3}*...*s^2_{r}$

根据唯一分解定理得:若有素数$p_1,p_2,p_3$,且$p_1 * p_2 = p^2_3(=Q)$,则$p_1=p_2=p_3$,即对Q的分解是唯一的.

因此有$s^2_i = a^2$,其中$a \in {p_i} \cup {q_i} $.

(博客公式处理有问题,下面放个截图吧……)

所以,对于$N*X$的所有质因数而言:

$N*X = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_k^{a_k}$

该式中$a^i$必然为偶数,但是由于:

$N = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_k^{a_k}$

该式中$a^i$不一定为偶数.(注意上面2式中同名变量无关)

因此,对于X的质因数分解,只需要保证能够和N的质因数分解"互补",即乘积的幂为偶数即可.

换句话说,为了求解X,初始令X=1,如果N的分解中某一个$p^{a^i}_i$,$a^i$为奇数,则$X*=p_i$;否则X不变.

之所以只乘$p_i$,即$p_i$的一次幂,而不是更高次,是因为要求X的最小值

分析到此结束,代码就是套用标准的质因数分解外加一些判断.

代码

使用C语言编写.

#include <stdio.h>

long long x = 1;

void primeFactorization(long long n) {
    int cnt = 0;
    for (long long i = 2; i * i <= n; ++i) {
        cnt = 0;
        while (n % i == 0) {
            n /= i;
            cnt++;
        }
        if (cnt & 1) { // 如果幂为奇数
            x *= i;
        }
    }
    if (n != 1) {
        x *= n; // 被这个卡了半天,仍有剩余说明当前n自身为素数(不一定是原始的n(?)),需要将
        // 它乘上
    }
}

int main() {
    long long n; // 注意数据范围
    scanf("%lld", &n);
    primeFactorization(n);
    printf("%lld", x);
    return 0;
}