「蓝桥杯」完全平方数（Java）

第十二届蓝桥杯省赛C++/JavaB组试题H

暴力枚举，TLE，过了7个样例，大概能拿到 50%~70% 的分数。

import java.util.Scanner;public class Main {    public static void main(String[] args) { Scanner sc = new Scanner(System.in); long n = sc.nextLong(); for (long i = 1; i <= n; i++) {     // 将这个数开根号之后转为整形 砍掉后面的小数位 判断是否等于这个数字     if ((long) Math.sqrt(i * n) * (long) Math.sqrt(i * n) == i * n) {  System.out.println(i);  return;     } }    }}

正解：其实本题的考点就是分解质因数， n ⋅ x = m 2 n·x=m^2 n⋅x=m2，$n$ 最小乘上多少，可以使得 $n$ 里面质因子的次数变为偶数；
n = P 1α1 × P 2α2 × . . . × P nαn n=P_1^{α1}×P_2^{α2}×...×P_n^{αn} n=P1α1​×P2α2​×...×Pnαn​，如果某项质因子的次数 α i α_i αi​ 是奇数，那我们就至少乘上这一个质因子，所以这道题就是把 $n$ 分解质因数，看一下它所有项的次数，把所有次数是奇数的质因子乘起来，就是答案。

时间复杂度 O ( N ) O(\sqrt N) O(N ​)

import java.util.Scanner;public class Main {    public static void main(String[] args) { Scanner sc = new Scanner(System.in); long n = sc.nextLong(); long res = 1; for (long i = 2; i * i <= n; i++) {     if (n % i == 0) {  int s = 0;  while (n % i == 0) { // 分解质因子求次数      s++;n /= i;  }  if (s % 2 == 1) res *= i; // 如果是奇数 则乘起来     } } if (n > 1) res *= n; // 表示还有一个质因子 次数是1  System.out.print(res);    }}

对于 $n>1$ 举例， 24 = 2 3 × 3 24 = 2^3×3 24=23×3，此时我们的 $res=2$，但还有一个因子 $3$ 没有算在内，因为我们的while(n % i == 0)中，最后一步代码n /= i = 3，还剩最后一个因子没有考虑，且次数为1，所以最后再乘上 $n$ 即可，$res=2\times 3=6$。

医疗百科