关于一些数论问题例题的讨论

  大概就是写一些数论水题的题解?


 

一.[AHOI2005]约数研究 洛谷oj P1403

  可能需要事先学习的算法:

    埃氏筛法(素数筛)

  题意很容易理解。很明显这是一道真正的水题,适合初学者理解筛法的思想。

  30分暴力做法

    对于一个数$i(i∈[1,n])$ ,枚举所有$[1,i)$之间的正整数$j$,判断$j$是否是$i$的约数,如果是,计数器$result$就加上1。

    复杂度是$O(n^2)$,不是很有讨论价值,写了一下代码。

关于一些数论问题例题的讨论
#include <cstdio>
using namespace std;

int n;
int result;

int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++)    //枚举 1~n 所有数 
        for (int j=1;j<=i;j++)    //一个个判断是否是i的约数,如果是,则计数加1 
            if (i%j==0)    result+=1;
    printf("%d",result);
    return 0;
}
View Code

 

  100分算法(暴力筛法):

    或许可以看成暴力做法的优化,但是如果学过筛法,那就直接是筛法的思想了。

    我试着用优化暴力的思路解释一下我的算法。上面的做法是先抓一个数$i(i∈[1,n])$,然后再一个个找它们的约数的。我们可以换个思路,也抓一个数$i(i∈[1,n])$,然后一个个找它的倍数(倍数小于$n$),找到一个倍数,计数器$result$就加上1。

    熟悉筛法的同学应该能一眼AC吧(毕竟是普及组水题)。

    复杂度应该是$O(n\sqrt{n})$。

 

#include <cstdio>
using namespace std;

int n;
int result;

int main(){
    scanf("%d",&n);
    result+=n;    //1可以是所有数的约数 
    for (int i=2;i<=n;i++)
        for (int j=1;i*j<=n;j++)    //枚举倍数 i*j 
            ++result;
    printf("%d",result);
    return 0;
}

    基于这种想法其实还可以优化。我们很容易发现,第二重循环其实是不必要的,因为对于一个数$i$,$[1,n]$里它的倍数一定有且仅有$\frac{n}{i}$个(向下取整)。那么我们就可以扔掉第二重循环了。

 

#include <cstdio>
using namespace std;

int n;
int result;

int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        result+=(n/i);
    printf("%d",result);
    return 0;
}

 

    是不是已经挺不错的了?但是洛谷上有神犇给出了下一种复杂度更加优秀的算法。

  100分算法(非常优秀):Kelin的题解

    大概意思是说,$f(i)=\frac{n}{i}$,但是因为除法要向下取整,所以有一些数可以当成同一个数来跳过。

    打个比方,对于$n=60$时,不管$i=13$或$i=14$或$i=15$,$\frac{n}{i}$的结果都是一样的,因为$int$整型要向下取整。所以可以把它们放在一起算,差不多就是这种思想。

    时间复杂度$O(2\sqrt{n})$。我测了一下,可能因为数据比较水,我写的算法$36ms$跑完,这种算法$26ms$跑完,还是十分优秀的。

    代码在上面链接里有,我就不写了。

 

二.最大公约数和最小公倍数问题  洛谷 P1029

  必须预先学习的算法:

    欧几里得算法(GCD)(辗转相除法)

  这是一道数论入门好题。在做之前要熟悉$gcd$(即最大公约数)。

  这题我觉得不太可能有靠谱的部分分写法(毕竟比较水),我就直接讲正解了。

  大家都知道怎么求最大公约数$gcd(P,Q)$,也许有人会问是不是也有专门求最小公倍数$lcm(P,Q)$的算法?不需要。最小公倍数$lcm(P,Q)$可以通过最大公约数$gcd(P,Q)$得到。

  引理:两个正整数$P$,$Q$的最小公倍数为$P*Q/gcd(P,Q)$。

  证明:

    记$P=gcd(P,Q)*p_{1}$

      $Q=gcd(P,Q)*p_{2}$,且$gcd(p_{1},p_{2})=1$  //即$p_{1}$和$p_{2}$互质

      $lcm(P,Q)=gcd(P,Q)*p_{1}*p_{2}$

          $=gcd(P,Q)*p_{1}*gcd(P,Q)*p_{2}/gcd(P,Q)$

          $=P*Q/gcd(P,Q)$

    得证。

   肯定有人不喜欢读证明,那我举个例子好了。假设存在两个数,$P=2160$,$Q=4032$。根据唯一分解定理,可得:

    $P=2160=2^4*3^3*5$

    $Q=4032=2^6*3^2*7$

  可以看出来,这时候$gcd(P,Q)=2^4*3^2=144$,那么,$P$和$Q$可以这样改写:

    $P=gcd(P,Q)*3^1*5$

    $Q=gcd(P,Q)*2^2*7$

  很明显,$3^1*5$或$2^2*7$互质,因为如果它们不互质,它们的最大公约数完全可以变成$gcd(P,Q)$的一个因子。

  又因为$lcm(P,Q)=2^6*3^3*5*7$,$lcm(P,Q)$具有$P$和$Q$的所有因子,则:

    $lcm(P,Q)=gcd(P,Q)*2^2*3^1*5*7$

         $=(gcd(P,Q)*3^1*5)*(gcd(P,Q)*2^2*7)/gcd(P,Q)$

         $=P*Q/gcd(P,Q)$

  就可以根据$lcm(P,Q)=P*Q/gcd(P,Q)$求解了。理解力好的同学应该可以直接理解这个结论。

  在知道$lcm(P,Q)=P*Q/gcd(P,Q)$后,再来看这道题。在这道题里,$x$是最大公约数$gcd(P,Q)$,而$y$是最小公倍数$lcm(P,Q)$。

  我们不妨设$P=x*p_{1}$,$Q=x*p_{2}$($p_{1}$和$p_{2}$互质)。

  所以我们可以写出下面的推导

    $y=P*Q/x$

      $=(x*p_{1})*(x*p_{2})/x$

      $=p_{1}*p_{2}*x$

    则$\frac{y}{x}=p_{1}*p_{2}$

  是不是发现了什么?题目要求输出的答案是$P$和$Q$,而$P=x*p_{1}$,$Q=x*p_{2}$,且$x$是已知的。要想知道$P$、$Q$的所有可能性,只需要枚举出$p_{1}$和$p_{2}$的所有可能性就好了。

  怎么枚举出$p_{1}$和$p_{2}$?我们已经知道$\frac{y}{x}=p_{1}*p_{2}$了,$for$一遍就好了。

  代码:

 

#include <cstdio>
using namespace std;
const int maxn=100000;

int x,y;
int result;

inline int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}

int main(){
    scanf("%d%d",&x,&y);
    if (y%x)    printf("0");    //如果y不能整除x,不存在解
    else{
        int n=y/x;
        for (int i=1;i<=n;i++)
            if (n%i==0){
                if (gcd(i,n/i)==1)
                    result+=1;
            }
        printf("%d",result);
    }
    return 0;
}

 

 

 

 

 

 

 

 

 

上一篇:洛谷 UVA11388 GCD LCM


下一篇:P1072 Hankson 的趣味题