唯一分解定理(算术基本定理)详解——hdu5248和lightoj1341-阿里云开发者社区

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

2022-10-19 303

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

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

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

定义：

任何一个大于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;
 //根据需求操作
 }
 //根据需求操作...
 }

打表：

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=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)));
      }
    }
  }
}

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];// 记录第几个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);
    }
  }
}

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

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

定义：

样例：

计算方法：

不打表：

打表：

唯一分解定义有什么用？

例题

附上ac代码：

埃氏筛

欧拉筛：

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

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

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

定义：

样例：

计算方法：

不打表：

打表：

唯一分解定义有什么用？

例题

附上ac代码：

埃氏筛

欧拉筛：

热门文章

最新文章

相关电子书