题目描述

巧用分解质因数

一个数A如果能组成完全平方数B，那么该完全平方数B一定能由A的质因子偶数次方形成。
如8可和2组成完全平方数16，而16=(2)^3×2=24，最后质因子的次数一定是偶数次方。

样例

import java.util.*;
public class Main{
    /*
       一般遇到这种数的题目你就去质因数和最小公倍数，就往上面猜，一猜一个准

       题意： n * x= m的二次方

       一个数A如果能组成完全平方数B，那么该完全平方数B一定能由A的质因子偶数次方形成。如8可和2组成完全平方数16，而16=(2)^3×2=24
       ，最后质因子的次数一定是偶数次方。

       所以，我们只要把n进行质因数分解，如果某个质因数的次数是奇数次，那么再乘上该质因数后的次数就为偶数次方了，就满足其性质。

       对于最后判断n > 1的举例： 假如 n 为24，按代码进行下去可知n=2^3×3，所以除了2还存在3这个质因子，那么24×(2×3)=144=12^2

    */

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        long n = sc.nextLong();
        long res = 1;

        for (long i = 2; i <= n / i; i ++ ){//枚举质因子  i <= n / i
            if (n % i == 0)
            {
                int s = 0;//统计质因子出现的次数
                while (n % i == 0){
                   s ++; //
                   n /= i; 
                } 
                //如果出现的次数为奇数 就乘上它
                if (s % 2 == 1) res *= i;
            } 
        }

        //说明还存在一个质因子，且它的次数为1，那就再乘上它。这个质因子是大于根号n的
        if (n > 1) res *= n;

        System.out.println(res);

    }
}