佛山优化网站,用node做的网站,wordpress 粘贴表格,招网络推广招聘文章目录 一、唯一分解定理是什么#xff1f;1.定义2.示例3.代码模板 二、例题1问题描述#xff08;2021蓝桥杯省赛#xff09;输入格式输出格式样例输入 1样例输出 1样例输入 2样例输出 2评测用例规模与约定 2解题思路3假娃3C嘎嘎 一、唯一分解定理是什么1.定义2.示例3.代码模板 二、例题1问题描述2021蓝桥杯省赛输入格式输出格式样例输入 1样例输出 1样例输入 2样例输出 2评测用例规模与约定 2解题思路3假娃3C嘎嘎 一、唯一分解定理是什么
1.定义
唯一分解定理是数论中的一个重要定理它告诉我们
任何大于 1 的正整数都可以唯一分解为若干个质数的乘积忽略排列顺序。
数学表达式 对于任意正整数 ( n 1 ) ( n 1 ) (n1)可以表示为 n p 1 e 1 × p 2 e 2 × ⋯ × p k e k n p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k} np1e1×p2e2×⋯×pkek 其中 ( p 1 , p 2 , … , p k ) ( p_1, p_2, \dots, p_k ) (p1,p2,…,pk) 是质数 ( e 1 , e 2 , … , e k ) ( e_1, e_2, \dots, e_k ) (e1,e2,…,ek) 是正整数 2.示例 12 的分解 12 2 2 × 3 1 12 2^2 \times 3^1 1222×31 质因数是 2 2 2 和 3 3 3。 100 的分解 100 2 2 × 5 2 100 2^2 \times 5^2 10022×52 质因数是 2 2 2 和 5 5 5。 修改后的格式如下 97 的分解 97 9 7 1 97 97^1 97971 97 97 97 是质数本身就是唯一分解。 3.代码模板
import java.util.*;
public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int nsc.nextInt();//Math.sqrt(n)可以进行时间优化for(int i2;iMath.sqrt(n);i){if(n%i0){int count0;//记录当前质数i的幂次while(n%i0){count;n/i;//除掉所有因子i}System.out.println(i count);//输出对应的因子 以及 它的幂次}}if(n1){//如果没有除完最后一个数一定是质因子System.out.println(n 1);//输出对应的因子 以及 它的幂次}}
}二、例题
1问题描述2021蓝桥杯省赛
一个整数 a a a 是一个完全平方数是指它是某一个整数的平方即存在一个整数 b b b使得 a b 2 a b^2 ab2。
给定一个正整数 n n n请找到最小的正整数 x x x使得它们的乘积是一个完全平方数。 输入格式
输入一行包含一个正整数 n n n。 输出格式
输出找到的最小的正整数 x x x。 样例输入 1
12样例输出 1
3样例输入 2
15样例输出 2
15评测用例规模与约定
对于 30 的评测用例 1 ≤ n ≤ 1000 1 \leq n \leq 1000 1≤n≤1000答案不超过 1000 1000 1000。对于 60 的评测用例 1 ≤ n ≤ 1 0 8 1 \leq n \leq 10^8 1≤n≤108答案不超过 1 0 8 10^8 108。对于所有评测用例 1 ≤ n ≤ 1 0 12 1 \leq n \leq 10^{12} 1≤n≤1012答案不超过 1 0 12 10^{12} 1012。 2解题思路
根据题意分析我们要求最小的 x x x 使得 x × n x\times n x×n 是一个完全平方数。 显而易见的是最坏情况 x x x 只能是 n n n本身。因此我们只需要在整数 n n n 以内去寻找最小的 x x x 即可。 结合唯一分解定理任何一个大于1的整数一定可以分解成一个或者多个质数也叫素数相乘。如果一个数是完全平方数则经过唯一分解后其质因子的幂次一定是偶数 例如 36 36 36 的分解 36 2 2 × 3 2 36 2^2 \times 3^2 3622×32 幂次 2 , 2 2, 2 2,2都是偶数 因此 36 36 36 是完全平方数。 144 144 144 的分解 144 2 4 × 3 2 144 2^4 \times 3^2 14424×32 幂次 4 , 2 4, 2 4,2都是偶数 因此 144 144 144 是完全平方数。 81 81 81 的分解 81 3 4 81 3^4 8134 幂次 4 4 4是偶数 因此 81 81 81 是完全平方数。 100 100 100 的分解 100 2 2 × 5 2 100 2^2 \times 5^2 10022×52 幂次 2 , 2 2, 2 2,2都是偶数 因此 100 100 100 是完全平方数。 72 72 72 的分解反例 72 2 3 × 3 2 72 2^3 \times 3^2 7223×32 幂次 3 , 2 3, 2 3,2 3 3 3 不是偶数 因此 72 72 72 不是完全平方数。
至此解题思路就很明了啦。唯一分解给定的 n n n 寻找其质因子如果质因子对应的幂次是奇数则需要补齐对应的一个质因子把它累乘到答案中即可。 3假娃
import java.util.*;// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);//测试用例数据规模比较大必须用longlong ans1;long nsc.nextLong();for(long i2;iMath.sqrt(n);i){if(n%i0){long count0;while(n%i0){count;n/i;}if(count%21){ans*i;}}}if(n1)ans*n;System.out.println(ans);}
}3C嘎嘎
#include iostream
#include cmath // 用于 sqrt 函数
using namespace std;int main() {long long ans 1; // 用 long long 处理大数long long n;cin n; // 输入 nfor (long long i 2; i sqrt(n); i) {if (n % i 0) { // 判断是否为因子long long count 0;while (n % i 0) { // 统计当前因子的幂次count;n / i;}if (count % 2 1) { // 如果幂次是奇数ans * i;}}}if (n 1) ans * n; // 如果 n 还大于 1则 n 本身是一个质数cout ans endl; // 输出结果return 0;
}
