|
大概就是寫一些數(shù)論水題的題解？ ? 一.[AHOI2005]約數(shù)研究 洛谷oj P1403 可能需要事先學(xué)習(xí)的算法： 埃氏篩法（素數(shù)篩） 題意很容易理解。很明顯這是一道真正的水題，適合初學(xué)者理解篩法的思想。 30分暴力做法： 對于一個數(shù)$i（i∈[1,n]）$ ，枚舉所有$[1,i)$之間的正整數(shù)$j$，判斷$j$是否是$i$的約數(shù)，如果是，計數(shù)器$result$就加上1。 復(fù)雜度是$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 所有數(shù)
for (int j=1;j<=i;j ) //一個個判斷是否是i的約數(shù)，如果是，則計數(shù)加1
if (i%j==0) result =1;
printf("%d",result);
return 0;
}
View Code
? 100分算法（暴力篩法）： 或許可以看成暴力做法的優(yōu)化，但是如果學(xué)過篩法，那就直接是篩法的思想了。 我試著用優(yōu)化暴力的思路解釋一下我的算法。上面的做法是先抓一個數(shù)$i（i∈[1,n]）$，然后再一個個找它們的約數(shù)的。我們可以換個思路，也抓一個數(shù)$i（i∈[1,n]）$，然后一個個找它的倍數(shù)（倍數(shù)小于$n$），找到一個倍數(shù)，計數(shù)器$result$就加上1。 熟悉篩法的同學(xué)應(yīng)該能一眼AC吧（畢竟是普及組水題）。 復(fù)雜度應(yīng)該是$O(n\sqrt{n})$。 ? #include <cstdio>
using namespace std;
int n;
int result;
int main(){
scanf("%d",&n);
result =n; //1可以是所有數(shù)的約數(shù)
for (int i=2;i<=n;i )
for (int j=1;i*j<=n;j ) //枚舉倍數(shù) i*j
result;
printf("%d",result);
return 0;
}
基于這種想法其實還可以優(yōu)化。我們很容易發(fā)現(xiàn)，第二重循環(huán)其實是不必要的，因為對于一個數(shù)$i$，$[1,n]$里它的倍數(shù)一定有且僅有$\frac{n}{i}$個（向下取整）。那么我們就可以扔掉第二重循環(huán)了。 ? #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;
}
? 是不是已經(jīng)挺不錯的了？但是洛谷上有神犇給出了下一種復(fù)雜度更加優(yōu)秀的算法。 100分算法（非常優(yōu)秀）：Kelin的題解 大概意思是說，$f(i)=\frac{n}{i}$，但是因為除法要向下取整，所以有一些數(shù)可以當(dāng)成同一個數(shù)來跳過。 打個比方，對于$n=60$時，不管$i=13$或$i=14$或$i=15$，$\frac{n}{i}$的結(jié)果都是一樣的，因為$int$整型要向下取整。所以可以把它們放在一起算，差不多就是這種思想。 時間復(fù)雜度$O(2\sqrt{n})$。我測了一下，可能因為數(shù)據(jù)比較水，我寫的算法$36ms$跑完，這種算法$26ms$跑完，還是十分優(yōu)秀的。 代碼在上面鏈接里有，我就不寫了。 ? 二.最大公約數(shù)和最小公倍數(shù)問題 洛谷 P1029 必須預(yù)先學(xué)習(xí)的算法： 歐幾里得算法（GCD）（輾轉(zhuǎn)相除法） 這是一道數(shù)論入門好題。在做之前要熟悉$gcd$（即最大公約數(shù)）。 這題我覺得不太可能有靠譜的部分分寫法（畢竟比較水），我就直接講正解了。 大家都知道怎么求最大公約數(shù)$gcd(P,Q)$，也許有人會問是不是也有專門求最小公倍數(shù)$lcm(P,Q)$的算法？不需要。最小公倍數(shù)$lcm(P,Q)$可以通過最大公約數(shù)$gcd(P,Q)$得到。
? 肯定有人不喜歡讀證明，那我舉個例子好了。假設(shè)存在兩個數(shù)，$P=2160$，$Q=4032$。根據(jù)唯一分解定理，可得： $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$互質(zhì)，因為如果它們不互質(zhì)，它們的最大公約數(shù)完全可以變成$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)$ 就可以根據(jù)$lcm(P,Q)=P*Q/gcd(P,Q)$求解了。理解力好的同學(xué)應(yīng)該可以直接理解這個結(jié)論。 在知道$lcm(P,Q)=P*Q/gcd(P,Q)$后，再來看這道題。在這道題里，$x$是最大公約數(shù)$gcd(P,Q)$，而$y$是最小公倍數(shù)$lcm(P,Q)$。 我們不妨設(shè)$P=x*p_{1}$，$Q=x*p_{2}$（$p_{1}$和$p_{2}$互質(zhì)）。 所以我們可以寫出下面的推導(dǎo) $y=P*Q/x$ ?$=(x*p_{1})*(x*p_{2})/x$ ?$=p_{1}*p_{2}*x$ 則$\frac{y}{x}=p_{1}*p_{2}$ 是不是發(fā)現(xiàn)了什么？題目要求輸出的答案是$P$和$Q$，而$P=x*p_{1}$，$Q=x*p_{2}$，且$x$是已知的。要想知道$P$、$Q$的所有可能性，只需要枚舉出$p_{1}$和$p_{2}$的所有可能性就好了。 怎么枚舉出$p_{1}$和$p_{2}$？我們已經(jīng)知道$\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 |
|
|
