唯一分解定理(算术基本定理)详解——hdu5248和lightoj1341
算数分解定理(唯一分解定理)：
定义：
任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积 N=P1a1 P2a2P3a3…Pnan，这里P1<P2<P3…<Pn均为质数，其中指数ai是正整数。这样的分解称为 N 的标准分解式.
应用：对于一个正整数n，如果n=q1a1 * q2 a2 * …* qnan,那么他的正因数个数为(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)=23*53.可以看的出来基本策略就是从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;
//根据需求操作
}
//根据需求操作...
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
打表：
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);//其他操作
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
唯一分解定义有什么用？
-
例如给一个1000，这样的数，问有多少种可能组合使得a * b=1000.或者求a*b中在那个范围内a，b的排列次数。
-
首先要了解一个唯一分解定理的应用：对于一个正整数n，如果n=q1a1 * q2 a2 * …* qnan,那么他的正因数个数为(1 a1) * (1 a2)…(1 an);对于这个，就可以衍生其他问题，比如找两个因数的组合情况，可能性，在那个范围等等。其实这就是一个组合问题。对于每一个数有t个，能够影响最终结果的就是这个素数出现的次数。如果细看虽然每个数的概率都是可能出现和不出现的1/2.但是对于最终结果就是：出现0次，出现1次，出现。。。，出现t次。所以这个数对结果出现的可能行变成了原来次数*（1 t）.以此类推，便可得到所有的因数可能的结果。
-
就例如1000=23 * 53:
对于结果首先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))); }
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
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);
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
欧拉筛：
import java.util.Scanner;
public class testC {
static int index=0;
public static void main(String[] args) {
// TODO 自动生成的方法存根
int prime[] = new int[100001];// 记录第几个prime
int 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);
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 如果对
后端、爬虫、数据结构算法等感性趣欢迎关注我的个人公众号交流：bigsai
文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。
原文链接：bigsai.blog.csdn.net/article/details/90479692
- 点赞
- 收藏
- 关注作者
评论（0）