唯一分解定理(算术基本定理)详解——hdu5248和lightoj1341

算数分解定理(唯一分解定理)：

定义：

任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积 N=P1^a1 P2^a2P3^a3…Pn^an，这里P1<P2<P3…<Pn均为质数，其中指数ai是正整数。这样的分解称为 N 的标准分解式.

应用：对于一个正整数n，如果n=q1^a1 * q2 ^a2 * …* qn^an,那么他的正因数个数为(1 a1) * (1 a2)* . . . *(1 an);

样例：

1000=2* 500=2* (2 * 250)=2 * 2 *( 2 * 125)=2 * 2 * 2 *(5 * 25)=2 * 2 * 2 * 5 * (5 *5)=2³*5³.可以看的出来基本策略就是从2开始除，直到不是2的倍数然后网上递增求。

计算方法：

计算n的分解方式。主要是通过数的自身对从最小的质数开始整除除一直到不能整除，直到跳出限制条件。

你可以从2到n;逐个遍历判断，满足条件的话就在数组中添加对应的count。当然，每被计算一次的时候，这个数就要被除一次。

上面方法对于大的数据显然复杂度太高。其实你可以从2遍历到根号n 1(i * i<n 1)停止，因为最大的理想乘积是i*i=n，其他的数据都是一个左，一个右面。最终分解的时候如果都分到这步了说明要么后面不剩，要么就是剩一个大质数。

上面虽然从数的量级减少了不少，但是会遍历很多没用的合数，比如遍历过2所有而的倍数都不需要遍历判断，所以我们只需要遍历素数。素数打表遍历素数，当遇到多组输入，数据要求较高的时候，先用素数筛打表，把素数预处理，然后直接从2-素数数组中遍历即可，因为如果一个数能被拆，那么他如果不能被拆，他就是素数，如果它还能被拆，那么它就是合数。所以一个数被分解到最后都是素数的次幂相乘！很重要！这样能够省的更多的时间。可以参考素数筛模板。

核心代码：
不打表：

for(int j=2;jj<n+1;j++) {while(n%j==0){n/=j;//根据需求操作}//根据需求操作...}

打表：

static int index=0;//根据数据范围范围内素数的最后一个位置prime[index] long prime[]=new long[100001]; boolean isprime[]=new boolean[1000001]; for(int i=2;i<1000001;i++)//埃拉托色尼筛选法 {if(!isprime[i]){prime[index ++]=i;for(int j=i+i;j<1000000;j=j+i){isprime[j]=true; }} } ........ ........// int n;for(int j=0;j<index;j++){if(n==0||prime[j]>n) {break;}//素数已经超出无法最大的数，退出long team=0;//其他操作，可以是你自己的逻辑while(c%prime[j]==0){c/=prime[j];team++ ;//其他操作}number*=(1+ team);//其他操作}

唯一分解定义有什么用？

• 例如给一个1000，这样的数，问有多少种可能组合使得a * b=1000.或者求a*b中在那个范围内a，b的排列次数。

• 首先要了解一个唯一分解定理的应用：对于一个正整数n，如果n=q1^a1 * q2 ^a2 * …* qn^an,那么他的正因数个数为(1 a1) * (1 a2)…(1 an);对于这个，就可以衍生其他问题，比如找两个因数的组合情况，可能性，在那个范围等等。其实这就是一个组合问题。对于每一个数有t个，能够影响最终结果的就是这个素数出现的次数。如果细看虽然每个数的概率都是可能出现和不出现的1/2.但是对于最终结果就是：出现0次，出现1次，出现。。。，出现t次。所以这个数对结果出现的可能行变成了原来次数*（1 t）.以此类推，便可得到所有的因数可能的结果。

• 就例如1000=2³ * 5³:
  对于结果首先2和5是独立互不影响的。所以对于一个因数。质数2的搭配有四种，出现0个，1个，2个或3个。同理质数5的搭配也是4种，所以最终因数可能出现的次数是4 * 4=1*(3 1)*(3 1)=16个。

例题

看下hdu5248

题意：给出n个数，求这n个数中最小的两个因数乘积，题意有些小的歧义不太好理解。说明白了就是让你从n个数分解找最小的两个因子相乘.(1不满足因为1没有2个及以上因子).

思路：数据量不大，可以不打表直接素数分解。其实每个数找到2个因子就可以停止了，放到list或者数组中，最后排序判断因子是否大于等于2个。按照要求输出

附上ac代码：

import java.util.ArrayList; import java.util.List; import java.util.Scanner;public class hdu5248 {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int T=sc.nextInt();for(int q=0;q<T;q++ ){int n=sc.nextInt();List<Long>list=new ArrayList<Long>();for(int i=0;i<n;i++){long te=sc.nextLong();int num=0;for(int j=2;(long)j*j<te+1;j++ ){while(te%j==0){list.add((long) j);te/=j;num ;}if(num>2)break;//其实找到两个就不用找了}if(te>1) {list.add(te);}}if(list.size()<2)System.out.println(-1);else {list.sort(null);System.out.println((long)(list.get(0)*list.get(1)));}}} }

lightoj1341
题目大意：给个面积s。一个边b，问最小边大于b的所有可能情况。
思路：整体-多余。先求出所有的排列次数，然后除以二（要求组合队数）。再从0头到b开始剪掉多余的情况。不需要考虑特大的那边，因为是对称的已经除以过二了。
ac代码：

埃氏筛

import java.util.Scanner; public class testC { static int index=0; public static void main(String[] args) {// TODO 自动生成的方法存根long prime[]=new long[100001];boolean isprime[]=new boolean[1000001];for(int i=2;i<1000001;i++)//埃拉托色尼筛选法{if(!isprime[i]){prime[index++]=i;for(int j=i +i;j<1000000;j=j+i){isprime[j]=true; }}}Scanner sc=new Scanner(System.in);int t=sc.nextInt();for(int i=0;i<t;i++){long a=sc.nextLong();long b=sc.nextLong();long number=1;long c=a;if(b*b>=a) {number=0;}//不可能的情况，最小边大于可能拼成的情况else {for(int j=0;j<index;j++){if(c==0||prime[j]>c) {break;}//超出界，跳出long team=0;while(c%prime[j]==0){c/=prime[j];team++;}number*=(1+team);//计算} if(c>1)number*=2;number/=2;//这里别被绕进去。这里不是按照次幂计算的，而是按照实打实的一个一个数判断的。for(int j=1;j<b;j++){if(a%j==0)number--;}}System.out.println("Case " (i+1) ": " +number);} }}

欧拉筛：

import java.util.Scanner;public class testC {static int index=0;public static void main(String[] args) {// TODO 自动生成的方法存根int prime[] = new int[100001];// 记录第几个primeint index = 0;boolean isprime[] = new boolean[1000001];for (int i = 2; i < 1000001; i++) {if (!isprime[i]) {prime[index++] = i;}for (int j = 0; j < index && i * prime[j] < 1000001; j++) {isprime[i * prime[j]] = true;// 找到的素数的倍数不访问if (i % prime[j] == 0)break;// 关键！！！！}}Scanner sc=new Scanner(System.in);int t=sc.nextInt();for(int i=0;i<t;i++){long a=sc.nextLong();long b=sc.nextLong();long number=1;long c=a;if(b*b>=a) {number=0;}//不可能的情况，最小边大于可能拼成的情况else {for(int j=0;j<index;j++){if(c==0||prime[j]>c) {break;}long team=0;while(c%prime[j]==0){c/=prime[j];team++;}number*=(1+team);} if(c>1)number*=2;number/=2;for(int j=1;j<b;j++){if(a%j==0)number--;}}System.out.println("Case " (i+1) ": " +number);}} }

• 如果对后端、爬虫、数据结构算法等感性趣欢迎关注我的个人公众号交流：bigsai

总结

以上是生活随笔为你收集整理的唯一分解定理(算术基本定理)详解——hdu5248和lightoj1341的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。