|
大概就是写一些数论水题的题解？ ? 一.[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=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;
}
? ? ? ? ? ? ? ? ? 来源：http://www./content-4-219951.html |
|
|
