郑州网站建设公司qq,wordpress多站点怎么修改域名,企业网络营销网站设计,2017建设厅网站唯一分解定理
1.内容
任何一个大于1的整数n都可以分解成若干个质数的连乘积#xff0c;如果不计各个质数的顺序#xff0c;那么这种分解是惟一的#xff0c;即若n1#xff0c;则有 n ∏ p i j n\prod{p^j_i} n∏pij 这里的 p i p_i pi是质数。可以进行简单证明…唯一分解定理
1.内容
任何一个大于1的整数n都可以分解成若干个质数的连乘积如果不计各个质数的顺序那么这种分解是惟一的即若n1则有 n ∏ p i j n\prod{p^j_i} n∏pij 这里的 p i p_i pi是质数。可以进行简单证明假设 p i p_i pi是合数那么它可以接着分解为两个数相乘的形式所以最后 p i p_i pi一定是质数。
2.唯一分解定理模板代码
模板代码其实也是唯一分解定理的直接应用给一个整数n问有多少个质数是n的约数。这里就需要进行分解也就是用到了唯一分解定理我们直接上代码然后逐一解释难懂的地方。
import java.util.Scanner;public class Main {
public static void main(String[] args) {Scanner scanner new Scanner(System.in);long n scanner.nextLong();int ans 0;for (int i 2; i Math.sqrt(n); i) {if(n%i0) ans;while(n%i 0) {n n / i;}}if(n 1) {ans;}System.out.println(ans);
}
}一般n可能给的很大注意最好用long类型 我们如果要求一个数的因数会从1开始遍历进行试除那么应该遍历到哪里呢是n吗其实遍历到 n \sqrt{n} n 就可以了。因为如果找到了一个因子为a那么大于 n \sqrt{n} n 的另一个因子就是n/a 很明显这个for循环我们是在采用试除法来求n的因子但是我们如何保证求到的因子是质因子呢这就是里面的while循环的作用了。给大家举个例子n366是它的因子但是不是质因子那么我们会不会遍历到它呢i2时在while循环里就把36里的所有2都除没了此时n9。i3时在while循环里就把36里的所有3都除没了此时n1。那么此时的n里面已经不包含6了因为6是由2和3构成的在遍历到6之前n里的所有的2和3都没有了自然也就没有6了。这就是while循环的作用他保证了我们找到的因子一定是质数。 抽象一点证明假设q是合数且是n的因子因为q是合数所有可以被表示成 q p 1 ∗ p 2 qp_1*p_2 qp1∗p2而 p 1 p_1 p1和 p 2 p_2 p2一定比q小那么他们一定会在while里面被除去因此遍历到q时不再包含它们自然也不会有q。 最后一个地方为什么在代码的最后要加一个if判断呢还是给大家举一个例子比如n396i2时n99。n3时n11。当i4时i n \sqrt{n} n 所以for循环退出了。但是你也可以发现11也是n的一个质因子所以我们在最后要判断一下防止把这种情况漏了。
练习题目
3.应用
1求正整数n的正因子个数
假设n的分解公式如下 n p 0 j 0 ∗ p 1 j 1 ∗ p 2 j 2 . . . ∗ p k j k np^{j_0}_0*p^{j_1}_1*p^{j_2}_2...*p^{j_k}_k np0j0∗p1j1∗p2j2...∗pkjk 则n的因子个数为 ( j 0 1 ) ∗ ( j 1 1 ) ∗ ( j 2 1 ) . . . ∗ ( j k 1 ) (j_01)*(j_11)*(j_21)...*(j_k1) (j01)∗(j11)∗(j21)...∗(jk1)个。
简单理解一下对于 2 3 ∗ 3 2 ∗ 5 3 2^{3}*3^{2}*5^{3} 23∗32∗53来说可以选择一个2其余质因子不选则2是其因子也可以选择两个2和一个3则12是其因子总的来说假设n包含m个质因子p则对于p我有m1中选择即[0,m]。
做个类比我有红球3个绿球5个他们共有多少种不同的组合肯定是46吧那么n的因子个数为 ( j 0 1 ) ∗ ( j 1 1 ) ∗ ( j 2 1 ) . . . ∗ ( j k 1 ) (j_01)*(j_11)*(j_21)...*(j_k1) (j01)∗(j11)∗(j21)...∗(jk1)同理。
模板代码如下
import java.util.Scanner;public class 约数个数 {
public static void main(String[] args) {Scanner scanner new Scanner(System.in);long n 1200000;int ans 1;for (int i 2; i Math.sqrt(n); i) {int cnt 0;while(n%i 0) {n n / i;cnt;}ans *(cnt1);}if(n 1) {ans * 2;}System.out.println(ans);
}
}
练习题目
2求正整数n的所有正因子之和
假设n的分解公式如下 n p 0 j 0 ∗ p 1 j 1 ∗ p 2 j 2 . . . ∗ p k j k np^{j_0}_0*p^{j_1}_1*p^{j_2}_2...*p^{j_k}_k np0j0∗p1j1∗p2j2...∗pkjk 则n的所有正因子之和为 s u m ( p 0 0 p 0 1 . . . p 0 j 0 ) ∗ ( p 1 0 p 1 1 . . . p 1 j 1 ) ∗ . . . ∗ ( p k 0 p k 1 . . . p k j k ) sum(p_0^0p_0^1...p_0^{j_0})*(p_1^0p_1^1...p_1^{j_1})*...*(p_k^0p_k^1...p_k^{j_k}) sum(p00p01...p0j0)∗(p10p11...p1j1)∗...∗(pk0pk1...pkjk)个。
这里如果正向推导的话不是很简单其实对于 p 0 0 p_0^0 p00而言能够和它相乘成为n的因子的数为 p 1 p_1 p1的幂次里选一个幂次 p 2 p_2 p2的幂次里选一个幂次… p k p_k pk的幂次里选一个幂次当然对于 p i p_i pi的幂次都会被选择只是不是同时被选择既然不是同时就把他们写成加法式子 p 0 0 ∗ ( p 1 0 p 1 1 . . . p 1 j 1 ) p_0^0*(p_1^0p_1^1...p_1^{j_1}) p00∗(p10p11...p1j1)表示的是从 p 1 p_1 p1的所有幂次里进行选择与 p 0 0 p_0^0 p00组成一个因子扩展到其它质数就是 p 0 0 ∗ ( p 1 0 p 1 1 . . . p 1 j 1 ) ∗ . . . ∗ ( p k 0 p k 1 . . . p k j k ) p_0^0*(p_1^0p_1^1...p_1^{j_1})*...*(p_k^0p_k^1...p_k^{j_k}) p00∗(p10p11...p1j1)∗...∗(pk0pk1...pkjk)然后再找对于 p 0 1 p_0^1 p01能够和它相乘成为n的因子的数可以表示为 p 0 1 ∗ ( p 1 0 p 1 1 . . . p 1 j 1 ) ∗ . . . ∗ ( p k 0 p k 1 . . . p k j k ) p_0^1*(p_1^0p_1^1...p_1^{j_1})*...*(p_k^0p_k^1...p_k^{j_k}) p01∗(p10p11...p1j1)∗...∗(pk0pk1...pkjk)把 p 0 p_0 p0的所有幂次都考虑到就是 ( p 0 0 p 0 1 . . . p 0 j 0 ) ∗ ( p 1 0 p 1 1 . . . p 1 j 1 ) ∗ . . . ∗ ( p k 0 p k 1 . . . p k j k ) (p_0^0p_0^1...p_0^{j_0})*(p_1^0p_1^1...p_1^{j_1})*...*(p_k^0p_k^1...p_k^{j_k}) (p00p01...p0j0)∗(p10p11...p1j1)∗...∗(pk0pk1...pkjk)
4.进阶题目
阶乘约数
问题描述 定义阶乘 n! 1 × 2 × 3 × ··· × n。
请问 100! 100 的阶乘有多少个约数。
答案提交 这是一道结果填空的题你只需要算出结果后提交即可。 本题的结果为一个整数在提交答案时只填写这个整数填写多余的内容将无法得分。
题目分析
这是蓝桥杯国赛的一道原题。求一个数的约数个数可以用唯一分解定理在 O ( n ) O(\sqrt{n}) O(n )的时间复杂度内求解。但是100的阶乘确实有点大了你要是把100的阶乘求出来再去求会超时并且这个数的存储也是一个问题当然用java的大整数是可以存的。
这里只能舍弃掉求100的阶乘再求它的约数个数的思路那应该怎么求呢回顾一下利用唯一分解定理求解约数个数的过程先对数字n进行质因数分解得到式子 n p 0 j 0 ∗ p 1 j 1 ∗ p 2 j 2 . . . ∗ p k j k np^{j_0}_0*p^{j_1}_1*p^{j_2}_2...*p^{j_k}_k np0j0∗p1j1∗p2j2...∗pkjk然后可以求得n的因子个数为 ( j 0 1 ) ∗ ( j 1 1 ) ∗ ( j 2 1 ) . . . ∗ ( j k 1 ) (j_01)*(j_11)*(j_21)...*(j_k1) (j01)∗(j11)∗(j21)...∗(jk1)。其实我们只需要知道数字n里面包含几个 p i p_i pi即可。对于 100 ! 1 ∗ 2 ∗ 3 ∗ 4... ∗ 100 100!1*2*3*4...*100 100!1∗2∗3∗4...∗100我们可以计算出2里面包含数字2的个数为 a 1 a_1 a13里面包含数字2的个数为 a 2 a_2 a24里面包含数字2的个数为 a 3 a_3 a35里面包含数字2的个数为 a 4 a_4 a4以此类推直到求到100那么100!里面包含数字2的个数就是 a 1 a 2 a 3 . . . a 99 a_1a_2a_3...a_{99} a1a2a3...a99。综上我们可以依次对1到100里面的每一个数进行质因数分解得到的值累加就可以了最终就可以求出来100进行质因子分解的结果。然后再按照求因子个数的方法进行求解就可以了。
题目代码
public class Main {
public static void main(String[] args) {int p[] new int[105];for(int i 2;i 100;i) {int n i;for(int j 2;j * j n;j) {while(n%j0) {p[j];n/j;}}if(n 0) p[n];}long ans 1;for(int i 2;i 100;i) {ans * (p[i]1);}System.out.println(ans);
}
}序列求和
问题描述 学习了约数后小明对于约数很好奇他发现给定一个正整数 t总是可 以找到含有 t 个约数的整数。小明对于含有 t 个约数的最小数非常感兴趣并 把它定义为 S t S_t St 。 例如 S 1 S_1 S1 1, S 2 S_2 S2 2, S 3 S_3 S3 4, S 4 S_4 S4 6···。 现在小明想知道前 60 个 S i S_i Si 的和是多少即 S 1 S 2 ⋅ ⋅ ⋅ S 60 S_1 S_2 ··· S_{60} S1S2⋅⋅⋅S60 是多少 答案提交 这是一道结果填空的题你只需要算出结果后提交即可。本题的结果为一 个整数在提交答案时只填写这个整数填写多余的内容将无法得分。
题目分析1
这也是蓝桥杯国赛的一道真题。参考题解
考虑一下i12时怎么求解 S i S_i Si 12 6 ∗ 2 126*2 126∗2 S i 2 5 ∗ 3 1 S_i2^5*3^1 Si25∗31 12 3 ∗ 2 ∗ 2 123*2*2 123∗2∗2 S i 2 3 ∗ 3 1 ∗ 5 1 S_i2^3*3^1*5^1 Si23∗31∗51 12 4 ∗ 3 124*3 124∗3 S i 2 3 ∗ 3 2 S_i2^3*3^2 Si23∗32 12 2 ∗ 2 ∗ 3 122*2*3 122∗2∗3 S i 2 1 ∗ 3 1 ∗ 5 2 S_i2^1*3^1*5^2 Si21∗31∗52
假设数字n的因数个数有12个那么根据12的分解结果可以推出来 S i S_i Si的值每个乘数间1就是要求的数分解后的质数的幂次但是这个值并不是唯一的不同的分解结果有不同的值同一个分解结果不同的幂次分配方式也对应不同的值。比如 12 2 ∗ 2 ∗ 3 122*2*3 122∗2∗3这种分解结果如果想要n的值比较小那么就把这几个数字分配到前3小的质数上即 S i 2 1 ∗ 3 1 ∗ 5 2 S_i2^1*3^1*5^2 Si21∗31∗52。但是这不是最理想的分配方式。我们将3,2,2降序排序再减一为2,1,1那么显然 S i 2 2 ∗ 3 1 ∗ 5 1 S_i2^2*3^1*5^1 Si22∗31∗51要比之前求的 S i 2 1 ∗ 3 1 ∗ 5 2 S_i2^1*3^1*5^2 Si21∗31∗52更小。
总结一下这道题的解题步骤对于 S i S_i Si我们dfs搜出i所有的分解情况然后按照刚刚的办法即对分解降序后求出 S i S_i Si。这样一种分解对应一个值所有的分解对应的值里面求最小值就是 S i S_i Si。
另外特判因子数为质数比如因子数是13减一是12这个幂次全部分配给2就是我们要找的最小数。
题目代码1
import java.math.BigInteger;
public class Main {static int n10000;static int prime[]new int[n];static int index0;static BigInteger endBigIntegernew BigInteger(99999999999999999999999999999999999);public static void main(String[] args) {int vis[]new int[n];for (int i 2; i n; i) {if (vis[i]0) {prime[index]i;index;for (int j i*i; j n; ji) {vis[j]1;}}}BigInteger sumBigIntegernew BigInteger(0);for (int i 1; i 60; i) {int vis1[]new int[i1];dfs(i,i,0,vis1);sumBigIntegersumBigInteger.add(endBigInteger);endBigIntegernew BigInteger(99999999999999999999999999999999999);}System.out.println(sumBigInteger);}static void dfs(int Snum,int mid,int start,int vis[]) {if (mid1) {if (endBigInteger.compareTo(loop(Snum, vis))1) {endBigIntegerloop(Snum, vis);}return;}for (int i 2; i mid; i) {if (mid%i0) {vis[i];dfs(Snum,mid/i, start, vis);dfs(Snum,mid/i, start1, vis);vis[i]--;}}}static BigInteger loop(int num,int vis[]) {int vis2[]new int[vis.length];for (int i 0; i vis.length; i) {vis2[i]vis[i];}int index20;BigInteger sumBigIntegernew BigInteger(1);for (int i vis2.length-1; i0; i--) {if (vis2[i]0) {sumBigIntegersumBigInteger.multiply(new BigInteger(prime[index2]).pow(i-1));vis2[i]--;ii1;}}return sumBigInteger;}
}题目分析2
刚刚的分析是比较正规但是也比较麻烦的思路这道题还有另外一种讨巧的思路。 S i S_i Si最多由4个质数构成要使值最小那么这4个质数必然是2357。我只需要枚举2357对应的幂次就可以了。在枚举的过程中记录当前有t个约数的值和之前记录的值取一个最小。最后求和输出就行。
题目代码2
import java.util.*;
public class Main {static int testCount60;static int ii100;static long result[]new long[61];public static void main(String[] args) {for (int a4 0; a4 ii; a4) {for (int a3 0; a3 ii; a3) {for (int a2 0; a2 ii; a2) {for (int a1 0; a1 ii; a1) {int t(a11)*(a21)*(a31)*(a41);if(t60) {long single(long) (Math.pow(2, a1)*Math.pow(3, a2)*Math.pow(5, a3)*Math.pow(7, a4));if(singleresult[t] || result[t]0) {result[t]single;}}}}}}long sum0;for (int i 1; i testCount; i) {sumresult[i];}System.out.println(sum);}
}
