本文共 1805 字，大约阅读时间需要 6 分钟。

目录

唯一分解定理

首先我们来了解一下什么是唯一分解定理。

任何一个正整数，都可以表示（分解）为所有素数（素数又叫质数，是因数只有两个的数）各种幂的积（1 = 任何素数 ^ 0，任何素数 = 自己 ^ 1），并且每个不同的数都只有一种分解，所以叫唯一分解定理。By the way，若一个数依次不被比自己小的素数整除，就可以判断它是素数。两个数的最大公约数就是这两个数的唯一分解式中重合的因子的积。一对互质数的分解中是没有重复的。

如 36 = 2 ^ 2 * 3 ^ 2 ( 2 * 2 * 3 * 3 ),   10 = 2 * 5。

[NOIP2001]最大公约数和最小公倍数问题

题目描述

输入两个正整数x0,y0(1≤x0＜100000，1≤y0≤1000000),求出满足下列条件的P,Q的个数 (1) P, Q是正整数 (2) 要求P,Q以x0为最大公约数, 以y0为最小公倍数. 试求:满足条件的所有可能的两个正整数的个数.

输入

x0,y0

输出

满足条件的P,Q的个数

样例输入

3  60

样例输出

4

分析+代码

这道题就要用到数论知识了，因为P，Q 都可以被x0整除，所以P，Q 可以表示为 a*x0 和 b*x0（a，b 为的正整数），我们都知道最小公倍数等于两个数的积 / 最大公约数，所以可以得到如下等式：

   a*x0 * b*x0 / x0 = y0

∴ a*x0 * b = y0

∴ a * b = y0 / x0

因为上式中全是整数，所以a和b都是 y0 / x0 的互质的因数。可以通过对 y0 / x0 唯一分解来解。

y0 / x0 = p1^w1  *  p2^w2  *  … *  pn^wn .（pi是素数，wi是幂）

就是要从这其中分出两个集合，一个积为a，一个积为b。

因为a和b互质，所以从中分出的两个集合中不能有重复的素数。题目最后要我们求的是有多少对P，Q，就是看有多少种分集合的方法。因此，wi的数量已经不重要了，答案取决于wi >= 1的 pi 的数量。每一个pi都有两种分法，要么去a，要么去b。有两个数就有2 * 2 = 4种分法。n个素数就有2 ^ n种分法。所以，整个代码就是求 y0 / x0 唯一分解式中有效素数的数量n，再输出 2 ^ n。

方法精妙，自己理解：

#include
   
    #include
    
     #include
     
      using namespace std;int read() {    int f = 1,x = 0;char s = getchar();    while(s < '0' || s > '9') {if(s == '-')f = -1;s = getchar();}    while(s >= '0' && s <= '9') {x = x * 10 + s - '0';s = getchar();}    return x * f;}int n,m,i,j,k,s,o,num;template
      
       T_ qkpow(T_ a,int e) {    if(e == 0) return T_(1);    if(e == 1) return a;    return pow(qkpow(a,e / 2),2) * qkpow(a,e % 2);}int main() {    n = read();m = read();    if(m % n) {        printf("0\n");        return 0;    }    m /= n;    for(i = 2;i <= n;i ++) {        if(m % i == 0) {            num ++;            while(m % i == 0) m /= i;//把m中的素数i全都除了，那么接下来判的因数i′就不被前面所有i整除，就是质因数了        }    }    if(m > 1) num ++;    printf("%d",int(pow(2,num)));    return 0;}
      
     
    
   

这道题一看代码很简单，数论题基本都有这样的特点，只是需要推理。

下一篇：

转载地址：https://blog.csdn.net/weixin_43960414/article/details/88177989 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！