寫這篇文章，可謂是頗費(fèi)了些周折，其實(shí)這篇文章早在３個(gè)星期以前就可以發(fā)了，一篇３０００多字的文章，由于一次死機(jī)，數(shù)據(jù)丟失而不得不重寫．第二次寫了一部分的時(shí)候干脆機(jī)器整個(gè)崩潰，無(wú)法開(kāi)機(jī)，直接報(bào)修去了．這是３次動(dòng)筆，三次思考得到的文章，我想，這次寫的東西可能會(huì)和第一第二次的內(nèi)容略有不同，但是這不會(huì)影響問(wèn)題的本質(zhì)，只不過(guò)換了個(gè)表現(xiàn)形式罷了．
不知道為什么，我突然想起了王勃著名的＜滕王閣序＞：＂時(shí)運(yùn)不濟(jì)， 命運(yùn)多舛。 馮唐易老， 李廣難封。 屈賈誼于長(zhǎng)沙， 非無(wú)圣主； 竄梁鴻于海曲， 豈乏明時(shí)。所賴君子見(jiàn)機(jī)，達(dá)人知命"．以前讀到這幾句，只覺(jué)他文筆好，卻未得其中深意，今天再度回首，終于能夠得以品匝出其中的苦澀厚味了．時(shí)運(yùn)不濟(jì)，命運(yùn)多舛啊..．昔日賈誼被扁長(zhǎng)沙，并非沒(méi)有明主（漢文帝），而梁鴻來(lái)到海曲，也并非是世道暗無(wú)天日之時(shí)（其實(shí)覺(jué)得賈誼用這個(gè)典故來(lái)抒懷比較牽強(qiáng):-P）。今天我們有明主明時(shí)，他它叫做“實(shí)力”，但是我們卻沒(méi)能逃過(guò)賈梁二人的結(jié)局，實(shí)在是令人扼腕嘆息。不過(guò)那又能說(shuō)明什么呢,魚(yú)頭有言，命運(yùn)決定于你對(duì)待問(wèn)題的態(tài)度，而不是結(jié)果，為什么我們又不能做到“窮且益堅(jiān)，不墜青云之志。酌貪泉而覺(jué)爽，處涸轍以猶歡。北海雖賒，扶搖可接；東隅已逝，桑榆非晚。孟嘗高潔，空懷報(bào)國(guó)之心；阮藉猖狂，豈效窮途之哭？”呢？，我們應(yīng)該善于抓住問(wèn)題的本質(zhì)，而不是區(qū)區(qū)一個(gè)結(jié)果。我必須承認(rèn)，這次的結(jié)局是不盡人意的，這讓我們錯(cuò)失了一個(gè)非常珍貴的機(jī)會(huì)（我相信這樣的機(jī)會(huì)不會(huì)太多），也沒(méi)有給魚(yú)頭一個(gè)滿意的答復(fù)，這個(gè)我是需要付絕對(duì)責(zé)任的。但是客觀地來(lái)看，勝敗乃兵家常事，有得有失，自然之理，有的人表面上成功了，其實(shí)他未必真具實(shí)力，而有些人表面上失敗了，但是也不見(jiàn)得此人沒(méi)有真才實(shí)學(xué)。我想，這都是正?，F(xiàn)象，只是不正常的地方在于，有的人抓住了一次機(jī)遇，就沾沾自喜，而另一些人結(jié)局杯具，就從此一蹶不振，殊不知，有的時(shí)候，只是機(jī)遇的天平倒向了另一側(cè)罷了。所以，對(duì)于把握住機(jī)遇的人，應(yīng)該認(rèn)真總結(jié)，彌補(bǔ)自己的不足，再接再礪，而對(duì)于失敗者，更應(yīng)該吸取教訓(xùn)與不足，讓自己的成功成為必然。所以，沒(méi)有絕對(duì)的成功者或是失敗者，We are all the same~ 我不想以失敗者的角度來(lái)寫這篇總結(jié)，原因上面已經(jīng)解釋得較為清楚，故不在贅述。
對(duì)于這次比賽，我們隊(duì)三個(gè)隊(duì)員的態(tài)度都是非常認(rèn)真的，從組隊(duì)的那一刻開(kāi)始，我們便針對(duì)將要來(lái)到的比賽做了較為細(xì)致的準(zhǔn)備。暑假回家以后，我們隊(duì)組織了三場(chǎng)練習(xí)比賽，通過(guò)這三次比賽，我們隊(duì)伍的合作能力得到了提高。我想，每一個(gè)隊(duì)員都把接下來(lái)的regional比賽看成是自己的頭等大事，我記得甚至在國(guó)慶放假的時(shí)候，我們都沒(méi)有忘記去POJ上練習(xí)，我記得我和阿義曾經(jīng)花了一整天的時(shí)間研究出圓和三角形的相交面積，我覺(jué)得這樣的態(tài)度是值得肯定的。然后便是五場(chǎng)網(wǎng)絡(luò)賽，在這幾場(chǎng)比賽中，我們不僅為集訓(xùn)隊(duì)貢獻(xiàn)了題目，而且也起到了鍛煉隊(duì)伍的作用。在這幾場(chǎng)比賽中，我們基本上能夠出三道以上的題目(當(dāng)然有很多題是因?yàn)楸蝗讼冗^(guò)掉所以就沒(méi)做了），我們應(yīng)該相信，我們?cè)趓egional的比賽中是能夠獲得滿意成績(jī)的。
然后便是上海之行了，作為第一次參加比賽的隊(duì)伍，我們的不確定因素有很多，多次比賽的經(jīng)驗(yàn)告訴我，他們不容易找到自己在整體中的位置，如果發(fā)揮得好，即使將王者趕下王座也不是不可能的。但若是狀態(tài)不好，可能結(jié)局也會(huì)比其他隊(duì)伍更糟糕一些。第一次參賽，可謂實(shí)力與運(yùn)氣并存，只是運(yùn)氣成分的比重稍微大一些吧。當(dāng)然，如果有事先鍛煉的機(jī)會(huì)，我想我是絕對(duì)會(huì)抓住的，哪怕只是一次現(xiàn)場(chǎng)賽的經(jīng)歷，因?yàn)楹玫男膽B(tài)是靠現(xiàn)場(chǎng)比賽積累出來(lái)的，可惜的是，竟然連一次這樣的機(jī)會(huì)也沒(méi)有。就好像是被抓來(lái)的壯丁被直接拉上了戰(zhàn)場(chǎng)一樣，槍都端不穩(wěn)，又如何打仗？
無(wú)論如何，我們還是在那個(gè)時(shí)間，那個(gè)地點(diǎn)，出現(xiàn)在了東華的體育場(chǎng)內(nèi)?？諝庠谶@個(gè)體育館里開(kāi)始凝固，感覺(jué)有點(diǎn)令人窒息。題目發(fā)下來(lái)之后，我看了前四題，華仔看中間3題，阿義看最后三題，我覺(jué)得我最大的失誤在于跳過(guò)了第一題，因?yàn)檫@個(gè)題讓人感覺(jué)是個(gè)比較難做的計(jì)算幾何題，和大家商量了一下之后，我決定跳過(guò)。。。然后看了第二題，第二題題目意思比較明白，就是求一個(gè)菲薄拉起數(shù)列，加一個(gè)A^Bmod c的操作，不過(guò)關(guān)鍵在于參數(shù)的值非常大。這個(gè)時(shí)候，張俊華發(fā)現(xiàn)后面的題沒(méi)有什么想法，于是回過(guò)頭來(lái)看第一題，看完之后，覺(jué)得這個(gè)題應(yīng)該屬于簡(jiǎn)單題，然后就開(kāi)始敲了，但是交上去,Wa了。這個(gè)時(shí)候 已經(jīng)陸陸續(xù)續(xù)升起了幾只黃色氣球，全場(chǎng)還是單色。所以我的感覺(jué)是這題一定是大家都能過(guò)的簡(jiǎn)單題，大家商量了一下，這個(gè)題應(yīng)該是最好過(guò)的，于是華仔和阿義繼續(xù)找錯(cuò)，我看其他的題目。不過(guò)近一個(gè)小時(shí)過(guò)去了，依然還是Wa。這個(gè)結(jié)果令人匪夷所思，難道此題有trick么？我不得不回身看了A題，抓住了幾個(gè)易錯(cuò)點(diǎn)，首先是1的對(duì)立狀態(tài)不一定是0，其次k還可以等于3.在這兩個(gè)地方，我們的程序都沒(méi)有考慮到。。。我想大家可能有些緊張了，唯一的辦法是快速AC這道題，才能緩解大家的緊張情緒。我想了想，直接枚舉邊不是更好么？復(fù)雜度只有64*64*64,雖然不愿意看到這樣的情況，但是我還是重寫了這道題，交上去，竟然是TLE!在此同時(shí)，我們嘗試暴力做了B題，還有那道最小生成樹(shù)的題，但都沒(méi)有AC,對(duì)于A題，雖然我盡量保持冷靜，再想各種各樣的剪枝，但是事后的情況告訴我，我還是遺漏掉一個(gè)細(xì)節(jié)，就是只有不同的狀態(tài)之間才可以交換，如果加上這個(gè)，可以剪去很多的時(shí)間。但我也沒(méi)有看到這處用下劃線標(biāo)記的句子，在這一點(diǎn)上，我需要對(duì)全隊(duì)負(fù)責(zé)。
如果可以抉擇的話，我寧愿將這樣的失利，放在省賽或者是邀請(qǐng)賽中，如果要用亞洲區(qū)決賽來(lái)積累經(jīng)驗(yàn)，這個(gè)代價(jià)未免太大了一些。只能說(shuō)，我們實(shí)在是大手筆了一次 呵呵^_^
賽后，我認(rèn)真的思考了這次的比賽，我覺(jué)得，大家的努力是值得肯定的。但是還有一些主觀和客觀因素制約著我們，我們的不足還有許多。我們參加的比賽比較少，經(jīng)驗(yàn)積累得少，這個(gè)無(wú)疑是很重要的一點(diǎn)。所以我們要抓住各種比賽的機(jī)會(huì)，主動(dòng)鍛煉自己的臨場(chǎng)狀態(tài)，這樣才能將自己的真正的實(shí)力轉(zhuǎn)化成為AC。
正如我前幾段里說(shuō)的那樣，一次成敗不足以論英雄，我們要不斷的完善自己，贏得主動(dòng)，而不是總等待著RP的爆發(fā)。呵呵，我突然想起了潤(rùn)之兄在長(zhǎng)征時(shí)寫的三首十六字令：
山，快馬加鞭未下鞍。驚回首，離天三尺三?！ ?
山，倒海翻江卷巨瀾。奔騰急，萬(wàn)馬戰(zhàn)猶酣。
山，刺破青天鍔（è）未殘。天欲墮，賴以拄其間。
在比賽中，我們需要這樣的大氣，需要這樣戰(zhàn)勝一切的信心和魄力，即使“天欲墮”，也要“賴以拄其間”！
（ 這篇文章寫得有些長(zhǎng)了，但愿大家還沒(méi)有視覺(jué)疲勞）今天我所說(shuō)的一切，只是針對(duì)一次的比賽，要知道，事情是不短變化發(fā)展中的，今天的經(jīng)驗(yàn)只能屬于過(guò)去，我們需要做的是用這有限的經(jīng)驗(yàn)去適應(yīng)無(wú)限變化的環(huán)境。所謂態(tài)度決定一切，我相信，通過(guò)我們的努力，大家終會(huì)有“更喜岷山千里雪，三軍過(guò)后盡開(kāi)顏"的一天！
By abilitytao
2009年11月28日夜
后來(lái)居然卡了一道2-sat，原來(lái)是將n寫成了m,小錯(cuò)誤總是不停的犯，也該到頭了吧～
6道2-sat題號(hào)
> POJ 3207 - Ikki's Story IV - Panda's Trick
> http://acm.pku.edu.cn/JudgeOnline/problem?id=3207
> POJ 3678 - Katu Puzzle
> http://acm.pku.edu.cn/JudgeOnline/problem?id=3678
> POJ 2723 - Get Luffy Out
> http://acm.pku.edu.cn/JudgeOnline/problem?id=2723
> POJ 3683 - Priest John's Busiest Day
> http://acm.pku.edu.cn/JudgeOnline/problem?id=3683
> POJ 2749 - Building roads
> http://acm.pku.edu.cn/JudgeOnline/problem?id=2749
> POJ 3648- Wedding
> http://acm.pku.edu.cn/JudgeOnline/problem?id=3648
如果一開(kāi)始我也用兩個(gè)dp數(shù)組就好了，但是我錯(cuò)誤地認(rèn)為如果從后往前掃描數(shù)組的話是不會(huì)出現(xiàn)相互影響的情況的，事實(shí)上我錯(cuò)了，原來(lái)數(shù)據(jù)里有重量為0的數(shù)據(jù)，如果有一對(duì)寶藏他們有兩種取法（如第二種情況）而這兩件寶物的重量又恰好為0，那么用 dp[j]=dp[j-w]+v[i] 這個(gè)狀態(tài)轉(zhuǎn)移方程相當(dāng)于兩件寶物都取了，這違背了題意，除了這一種情況之外，其他的情況都可以直接用上面的轉(zhuǎn)移方程式（所以說(shuō)這個(gè)題真的很猥瑣，但也體現(xiàn)出我對(duì)背包問(wèn)題掌握的不全面）。
當(dāng)我知道了這個(gè)陷阱后，我極力的想證明只有都是0的情況才不能用上面的方法，所以我只開(kāi)了一個(gè)dp數(shù)組，事實(shí)上證明我是正確的！這個(gè)題糾結(jié)了較長(zhǎng)時(shí)間，雖然能比當(dāng)場(chǎng)做出來(lái)的同學(xué)想的更清晰，但是總是現(xiàn)場(chǎng)卡題也不是個(gè)好現(xiàn)象，有則改之吧。
#include<iostream>
using namespace std;
#define max(a,b) (a>b?a:b)
#define MAX 10001
struct node
{
int w1,v1,w2,v2,flag;
}l[MAX];
int dp[50001];
int main()
{
int bagw;
int n;
int i,j;
while(scanf("%d%d",&bagw,&n)!=EOF)
{
bagw/=100;
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
{
scanf("%d%d%d%d%d",&l[i].w1,&l[i].v1,&l[i].w2,&l[i].v2,&l[i].flag);
l[i].w1/=100;
l[i].w2/=100;
}
for(i=1;i<=n;i++)
{
for(j=bagw;j>=0;j--)
{
int temp=dp[j];
if(l[i].flag==1)
{
int pos=j-l[i].w1-l[i].w2;
if(pos>=0)
dp[j]=max(dp[j],dp[pos]+l[i].v1+l[i].v2);
}
if(l[i].flag==2)
{
int pos=j-l[i].w1;
if(pos>=0)
{
if(max(dp[j],dp[pos]+l[i].v1)>temp)
{
temp=max(dp[j],dp[pos]+l[i].v1);
}
}
pos=j-l[i].w2;
if(pos>=0)
{
if(max(dp[j],dp[pos]+l[i].v2)>temp)
temp=max(dp[j],dp[pos]+l[i].v2);
}
dp[j]=temp;
}
if(l[i].flag==3)
{
int pos=j-l[i].w1;
if(pos>=0)
{
if(max(dp[j],dp[pos]+l[i].v1)>temp)
{
temp=max(dp[j],dp[pos]+l[i].v1);
}
}
pos=j-l[i].w1-l[i].w2;
if(pos>=0)
{
if(max(dp[j],dp[pos]+l[i].v1+l[i].v2)>temp)
{
temp=max(dp[j],dp[pos]+l[i].v1+l[i].v2);
}
}
dp[j]=temp;
}
}
}
int res=0;
for(i=1;i<=bagw;i++)
{
if(res<dp[i])
res=dp[i];
}
printf("%d\n",res);
}
return 0;
}
topcoder SRM 又快到了，希望自己能正常發(fā)揮，不過(guò)這次是DIV 1了，希望題目不要太難 ，呵呵 加油啦 ^_^
Problem Statement
|
| |
There are N cities in a country, numbered 0 to N-1. Each pair of cities is connected by a bidirectional road.
John plans to travel through the country using the following rules:
- He must start in one city and end in another city after travelling exactly N-1 roads.
- He must visit each city exactly once.
- You are given a String[] roads. If the j-th character of the i-th element of roads is 'Y', he must travel the road that connects city i and city j.
For example, if there are three cities, and he wants to travel the road between city 0 and city 1, there are 4 possible paths: 0->1->2, 1->0->2, 2->0->1, 2->1->0. Paths 0->2->1 and 1->2->0 are not allowed because they do not allow him to travel the road between city 0 and city 1.
Return the number of paths he can choose, modulo 1,000,000,007. |
Definition
|
| |
| Class: |
HamiltonPath |
| Method: |
countPaths |
| Parameters: |
String[] |
| Returns: |
int |
| Method signature: |
int countPaths(String[] roads) |
| (be sure your method is public) |
|
| |
|
Constraints
|
| - |
roads will contain between 2 and 50 elements, inclusive. |
| - |
Each element of roads will contain n characters, where n is the number of elements in roads. |
| - |
Each character in roads will be 'Y' or 'N'. |
| - |
The i-th character in the i-th element of roads will be 'N'. |
| - |
The j-th character in the i-th element of roads and the i-th character in the j-th element of roads will be equal. |
Examples
|
| 0) |
|
| |
|
|
Returns: 4
|
| The example from the problem statement. |
|
|
| 1) |
|
| |
{"NYYY",
"YNNN",
"YNNN",
"YNNN"}
|
|
Returns: 0
|
| It's impossible to travel all these roads while obeying the other rules. |
|
|
| 2) |
|
| |
|
| 3) |
|
| |
{"NNNNNY",
"NNNNYN",
"NNNNYN",
"NNNNNN",
"NYYNNN",
"YNNNNN"}
|
|
Returns: 24
|
|
|
|
求哈密頓通路的數(shù)目，題目中指定了一些道路必須經(jīng)過(guò)。
1。做法是求連通分支，縮點(diǎn)，并判斷有沒(méi)有出現(xiàn)環(huán)或者非正常情況，若出現(xiàn)直接返回0。
2。求連通分支數(shù)的全排列；
3。遍歷所有連通分支
4。如果該連通分支擁有的點(diǎn)數(shù)>=2,則結(jié)果乘以2，即可得到答案.
求的時(shí)候要注意mod操作，要用long long 保存中間數(shù)據(jù)，(a*b)mod c中 a*b可能溢出32位整數(shù)。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<string>
using namespace std;
int graph[51][51];
int n;
int v[51];
int ID[51];
int num[51];
int gcc=0;
int flag=0;
void dfs(int f,int k)
{
if(flag==1)
return;
ID[k]=gcc;
num[gcc]++;
int i;
for(i=1;i<=n;i++)
{
if(graph[k][i]&&(v[i]==1)&&(i!=f))
{
flag=1;
return;
}
if(graph[k][i]&&(v[i]==0))
{
v[i]=1;
dfs(k,i);
}
}
}
class HamiltonPath
{
int i,j;
public:
int countPaths(vector <string> roads)
{
n=roads[0].length();
for(i=0;i<n;i++)
{
for(j=0;j<=n;j++)
{
if(roads[i][j]=='Y')
graph[i+1][j+1]=1;
}
}
for(i=1;i<=n;i++)
{
if(!v[i])
{
v[i]=1;
gcc++;
dfs(-1,i);
}
}
if(flag==1)
return 0;
int cnt=0;
for(i=1;i<=n;i++)
{
cnt=0;
for(j=1;j<=n;j++)
{
if(graph[i][j]==1)
cnt++;
}
if(cnt>2)
return 0;
}
long long res=1;
for(i=1;i<=gcc;i++)
{
res*=i;
res%=1000000007;
if(num[i]>=2)
{
res*=2;
res%=1000000007;
}
}
return res;
}
};
第一次寫tc,寫的不好還請(qǐng)大家多多指點(diǎn) :-)
Introduction
Suppose you had some large number that you knew was not a prime number and you needed to find out what its factors are. How would you go about doing that? You could try dividing it by 2, 3, 4, 5, etc. until you find one that works. You could even optimize that a bit if you by only trying to divide by prime numbers. But, if the smallest divisor of your number is pretty large, you've got a great deal of work ahead of you.
John Pollard published his Rho Method of Factorization in 1974. It takes advantage of some properties of divisors of numbers to zoom in on a factor quite quickly. Once you have one factor, you can readily break the original number into two smaller numbers to factor.
This is a brief description of the Pollard's Rho Algorithm. If you're already familiar with modulo arithmetic and greatest common divisors, you can skip ahead to the actual algorithm.
Modulo Arithmetic
If you're already comfortable with addition, subtraction, multiplication, and exponentiation modulo a number, feel free to skip over this whole section.
Definition Modulo
Two numbers x and y are defined to be congruent modulo n if their difference (x-y) is an integer multiple of n. Another way of stating this is to say that x and y both have the same remainder when divided by n.
For example, suppose that x = qx*n + rx where 0 <= rx< n. And, suppose that y = qy*n + ry where 0 <= ry< n. Then, x is congruent to y modulo n if and only if rx = ry. You can see that if rx = ry, then (x-y) is just
qx*n - qy*n + rx - ry = (qx-qy) * n
For a concrete example, suppose that x = 37, y = -14 and n = 17. x is congruent to y modulo n. We know this because
(x-y) = 37 + 14 = 51 = 3*17
We could also tell this because x = 2*17 + 3 and y = (-1)*17 + 3—both have a remainder of 3 when divided by 17. By the same logic, it is also easy to see that both x and y are congruent to 3 since 3 = 0*17 + 3.
Modulo Operations
We often speak of doing some operation (addition, subtraction, multiplication, etc.) “modulo n”. This simply means, do the operation and then rewrite the answer to be the number that's at least 0, is less than n, and is congruent modulo n with the answer.
For example, 37 + 15 = 1 modulo n. This is often abbreviated like this:
37 + 15 = 1 (mod n)
Conveniently, one can take any number in a modulo equation and replace it with any number which is congruent to it. It is usually convenient to pick the smallest positive number which foots the bill. So, we could redo the equation 37 + 15 = 1 without having to add those huge numbers 37 and 15 or to divide that huge sum of 52 by 17. Instead, we could replace the 37 with 3 because they are congruent with each other modulo 17. So,
37 + 15 = 3 + 15 = 18 = 1 (mod n)
The same thing holds for subtraction and for multiplication and for exponentiation. So, it is easy to see that 374 = 13 modulo 17. We simply replace the 37 by 3. Then, we break up the exponentiation a bit.
374 = 34 = ( 33 )*3 = 27 * 3 = 10 * 3 = 30 = 13
because 27 = 10 and 30 = 13 modulo 17.
Greatest Common Divisor (Euclidean Algorithm)
For Pollard's Rho Method, one needs to be able to find the Greatest Common Divisor of two numbers. The Greatest Common Divisor is the largest number which divides evenly into each of the original numbers. The Greatest Common Divisor of a and b is often written “gcd(a,b)”. Sometimes, you will see it written simply as “(a,b)”.
The Greatest Common Divisor is symmetric. This is
gcd(a,b) = gcd(b,a)
The usual method for finding the Greatest Common Divisor is the Euclidean Algorithm. The Euclidean Algorithm goes like this.... Start with the numbers a and b. Express a as a multiple of b plus a remainder r which is greater than or equal to zero and less than b. If r is greater than zero, set a equal to b and set b equal to r. Lather. Rinse. Repeat.
As you can see, r decreases every iteration until it reaches zero. On the first pass, it cannot be as big as b. On the second pass, it cannot be as big as it was on the first pass. On the n-th pass, it cannot be as big as it was on the previous pass. Eventually, r has to get to zero. When it does, then b (which was the previous r) is the Greatest Common Divisor of the original a and b. [Actually, if the original b is some multiple of the original a, then the first r will be zero. In that case, the Greatest Common Divisor will actually be a instead of b. You can avoid this problem by always starting with a being the number which has the highest absolute value.]
For example, let us find the Greatest Common Divisor of 658 and 154. This leads to the following sequence of equations.
658 = 4 * 154 + 42
154 = 3 * 42 + 28
42 = 1 * 28 + 14
28 = 2 * 14 + 0
Which means that 14 is the greatest common divisor of 658 and 154.
You can see that 14 divides evenly into 154 and 168 by propagating back up the that list of equations. The last equation shows that 14 divides into 28. The equation before that shows that 42 is some multiple of something which is a multiple of 14 with an extra 14 tacked on the end. This means that 42 is a multiple of 14 since it is the sum of two things which are multiples of 14. The equation above that shows that 154 is the sum of a multiple of 42 and 28. Both 42 and 28 are multiples of 14, so 154 is also a multiple of 14. And, the last equation, by similar logic, shows that 658 is divisible by 14.
Unfortunately, in the preceding paragraph, we only managed to show that 14 was a common divisor of 658 and 154. We didn't show that it was necessarily the largest divisor common to both. That part is more complicated. At the time of writing here, I don't feel like getting into that. You can find ample documentation of the Euclidean Algorithm in text books and on the web if you're interested in that part of the proof.
Now, on to the actual algorithm.
The Algorithm
Say, for example, that you have a big number n and you want to know the factors of n. Let's use 16843009. And, say, for example, that we know that n is a not a prime number. In this case, I know it isn't because I multiplied two prime numbers together to make n. (For the crypto weenies out there, you know that there a lot of numbers lying around which were made by multiplying two prime numbers together. And, you probably wouldn't mind finding the factors of some of them.) In cases where you don't know, a priori, that the number is composite, there are a variety of methods to test for compositeness.
Let's assume that n has a factor d. Since we know n is composite, we know that there must be one. We just don't know what its value happens to be. But, there are some things that we do know about d. First of all, d is smaller than n. In fact, there are at least some d which are no bigger than the square root of n.
So, how does this help? If you start picking numbers at random (keeping your numbers greater or equal to zero and strictly less than n), then the only time you will get a = b modulo n is when a and b are identical. However, since d is smaller than n, there is a good chance that a = b modulo d sometimes when a and b are not identical.
Well, if a = b (mod d), that means that (a-b) is a multiple of d. Since n is also a multiple of d, the greatest common divisor of (a-b) and n is a positive, integer multiple of d. So, now, we can divide n by whatever this greatest common divisor turned out to be. In doing so, we have broken down n into two factors. If we suspect that the factors may be composite, we can continue trying to break them down further by doing the algorithm again on each half.
The amazing thing here is that through all of this, we just knew there had to be some divisor of n. We were able to use properies of that divisor to our advantage before we even knew what the divisor was!
This is at the heart of Pollard's rho method. Pick a random number a. Pick another random number b. See if the greatest common divisor of (a-b) and n is greater than one. If not, pick another random number c. Now, check the greatest common divisor of (c-b) and n. If that is not greater than one, check the greatest common divisor of (c-a) and n. If that doesn't work, pick another random number d. Check (d-c), (d-b), and (d-a). Continue in this way until you find a factor.
As you can see from the above paragraph, this could get quite cumbersome quite quickly. By the k-th iteration, you will have to do (k-1) greatest common divisor checks. Fortunately, there is way around that. By structuring the way in which you pick “random” numbers, you can avoid this buildup.
Let's say we have some polynomial f(x) that we can use to pick “random” numbers. Because we're only concerned with numbers from zero up to (but not including) n, we will take all of the values of f(x) modulo n. We start with some x1. We then choose to pick our random numbers by xk+1 = f(xk).
Now, say for example we get to some point k where xk = xj modulo d with k < j. Then, because of the way that modulo arithmetic works, f(xk) will be congruent to f(xj) modulo d. So, once we hit upon xk and xj, then each element in the sequence starting with xk will be congruent modulo d to the corresponding element in the sequence starting at xj. Thus, once the sequence gets to xk it has looped back upon itself to match up with xj (when considering them modulo d).
This looping is what gives the Rho method its name. If you go back through (once you determine d) and look at the sequence of random numbers that you used (looking at them modulo d), you will see that they start off just going along by themselves for a bit. Then, they start to come back upon themselves. They don't typically loop the whole way back to the first number of your sequence. So, they have a bit of a tail and a loop---just like the greek letter “rho”.
Before we see why that looping helps, we will first speak to why it has to happen. When we consider a number modulo d, we are only considering the numbers greater than or equal to zero and strictly less than d. This is a very finite set of numbers. Your random sequence cannot possibly go on for more than d numbers without having some number repeat modulo d. And, if the function f(x) is well-chosen, you can probably loop back a great deal sooner.
The looping helps because it means that we can get away without piling up the number of greatest common divisor steps we need to perform. In fact, it makes it so that we only need to do one greatest common divisor check for every second random number that we pick.
Now, why is that? Let's assume that the loop is of length t and starts at the j-th random number. Say that we are on the k-th element of our random sequence. Furthermore, say that k is greater than or equal to j and t divides k. Because k is greater than j we know it is inside the looping part of the Rho. We also know that if t divides k, then t also divides 2*k. What this means is that x2*k and xk will be congruent modulo d because they correspond to the same point on the loop. Because they are congruent modulo d, their difference is a multiple of d. So, if we check the greatest common divisor of (xk-xk/2) with n every time we get to an even k, we will find some factor of n without having to do k-1 greatest common divisor calculations every time we come up with a new random number. Instead, we only have to do one greatest common divisor calculation for every second random number.
The only open question is what to use for a polynomial f(x) to get some random numbers which don't have too many choices modulo d. Since we don't usually know much about d, we really can't tailor the polynomial too much. A typical choice of polynomial is
f(x) = x2 + a
where a is some constant which isn't congruent to 0 or -2 modulo n. If you don't place those restrictions on a, then you will end up degenerating into the sequence { 1, 1, 1, 1, ... } or { -1, -1, -1, -1, ... } as soon as you hit upon some x which is congruent to either 1 or -1 modulo n.
Examples
Let's use the algorithm now to factor our number 16843009. We will use the sequence x1=1 with xn+1 = 1024*xn2 + 32767 (where the function is calculated modulo n). [ I also tried it with the very basic polynomial f(x) = x2 + 1, but that one went 80 rounds before stopping so I didn't include the table here.]
| k |
xk |
gcd( n, xk-xk/2 ) |
| 1 |
1 |
| 2 |
33791 |
1 |
| 3 |
10832340 |
| 4 |
12473782 |
1 |
| 5 |
4239855 |
| 6 |
309274 |
0 |
| 7 |
11965503 |
| 8 |
15903688 |
1 |
| 9 |
3345998 |
| 10 |
2476108 |
0 |
| 11 |
11948879 |
| 12 |
9350010 |
1 |
| 13 |
4540646 |
| 14 |
858249 |
0 |
| 15 |
14246641 |
| 16 |
4073290 |
0 |
| 17 |
4451768 |
| 18 |
14770419 |
257 |
Let's try to factor again with a different random number schema. We will use the sequence x1=1 with xn+1 = 2048*xn2 + 32767 (where the function is calculated modulo n).
| k |
xk |
gcd( n, xk-xk/2 ) |
| 1 |
1 |
| 2 |
34815 |
1 |
| 3 |
9016138 |
| 4 |
4752700 |
1 |
| 5 |
1678844 |
| 6 |
14535213 |
257 |
There is an art to picking the polynomial. I don't know that art at all. I tried a couple of polynomials until I found one that zoomed in relatively quickly. If I had to factor something with this method, I would generate a few small polynomials at random and try them out in parallel until one of them found a factor or I got tired of waiting
copy from:http://www.csh.rit.edu/~pat/math/quickies/rho/#algorithm
這個(gè)文章主要介紹了3算法
1線性時(shí)間篩素?cái)?shù)
2線性時(shí)間求前n個(gè)數(shù)的歐拉函數(shù)值
3線性時(shí)間求前n個(gè)數(shù)的約數(shù)個(gè)數(shù)
一、 首先介紹下積性函數(shù)。
下面是wiki的條目：
在非數(shù)論的領(lǐng)域，積性函數(shù)指有對(duì)于任何a,b都有性質(zhì)f(ab)=f(a)f(b)的函數(shù)。
在數(shù)論中的積性函數(shù)。對(duì)于正整數(shù)n的一個(gè)算術(shù)函數(shù)f(n)，當(dāng)中f(1)=1且當(dāng)a,b互質(zhì)，f(ab)=f(a)f(b)，在數(shù)論上就稱它為積性函數(shù)。
若某算術(shù)函數(shù)f(n)符合f(1)=1，且就算a,b不互質(zhì)，f(ab)=f(a)f(b)，稱它為完全積性的。
例子
φ(n) －歐拉φ函數(shù)，計(jì)算與n互質(zhì)的正整數(shù)之?dāng)?shù)目
μ(n) －默比烏斯函數(shù)，關(guān)于非平方數(shù)的質(zhì)因子數(shù)目
gcd(n,k) －最大公因子，當(dāng)k固定的情況
d(n) －n的正因子數(shù)目
σ(n) －n的所有正因子之和
σk(n): 因子函數(shù)，n的所有正因子的k次冪之和，當(dāng)中k可為任何復(fù)數(shù)。在特例中有：
σ0(n) = d(n) 及
σ1(n) = σ(n)
1(n) －不變的函數(shù)，定義為 1(n)=1 （完全積性）
Id(n) －單位函數(shù)，定義為 Id(n)=n （完全積性）
Idk(n) －冪函數(shù)，對(duì)于任何復(fù)數(shù)、實(shí)數(shù)k，定義為Idk(n) = nk （完全積性）
Id0(n) = 1(n) 及
Id1(n) = Id(n)
ε(n) －定義為：若n = 1，ε(n)=1；若n > 1，ε(n)=0。有時(shí)稱為“對(duì)于狄利克雷回旋的乘法單位”（完全積性）
(n/p) －勒讓德符號(hào)，p是固定質(zhì)數(shù)（完全積性）
λ(n) －劉維爾函數(shù)，關(guān)于能整除n的質(zhì)因子的數(shù)目
γ(n)，定義為γ(n)=(-1)ω(n)，在此加性函數(shù)ω(n)是不同能整除n的質(zhì)數(shù)的數(shù)目
所有狄利克雷特性均是完全積性的
二、再介紹下線性篩素?cái)?shù)方法
bool notp[mr];//素?cái)?shù)判定
__int64 pr[670000],pn,ans;//pr存放素?cái)?shù),pn當(dāng)前素?cái)?shù)個(gè)數(shù)。
void getprime()
{
pn=0;
memset(notp,0,sizeof(notp));
for(int i=2;i<mr;i++)
{
if(!notp[i])pr[pn++]=i;
for(int j=0;j<pn && pr[j]*i<mr;j++)
{
notp[pr[j]*i]=1;
if(i%pr[j]==0)break;
}
}
}
利用了每個(gè)合數(shù)必有一個(gè)最小素因子。
每個(gè)合數(shù)僅被它的最小素因子篩去正好一次。所以為線性時(shí)間。
代碼中體現(xiàn)在：
if(i%pr[j]==0)break;
pr數(shù)組中的素?cái)?shù)是遞增的,當(dāng)i能整除pr[j]，那么i*pr[j+1]這個(gè)合數(shù)肯定被pr[j]乘以某個(gè)數(shù)篩掉。
因?yàn)?span>i中含有pr[j],pr[j]比pr[j+1]小。接下去的素?cái)?shù)同理。所以不用篩下去了。
在滿足i%pr[j]==0這個(gè)條件之前以及第一次滿足改條件時(shí),pr[j]必定是pr[j]*i的最小因子。
三、結(jié)合線性篩素?cái)?shù)算法的優(yōu)化算法
基于這個(gè)線性篩素?cái)?shù)算法,我們可以很容易地得到某個(gè)數(shù)的最小素因子。
因?yàn)楫?dāng)i%pr[j]!=0的時(shí)候,最小素因子pr[j]與i互質(zhì),滿足積性函數(shù)的條件,可以直接得到f(i*pr[j])=f(i)*f(pr[j]).
不過(guò)當(dāng)i%pr[j]==0時(shí)我們必須根據(jù)該積性函數(shù)本身的特性進(jìn)行計(jì)算.或者在篩的同時(shí)保存并遞推些附加信息.總之要O(1)求得f(i*pr[j])及完成遞推附加信息.
下面的兩個(gè)例子是歐拉函數(shù)phi和約數(shù)個(gè)數(shù).這兩個(gè)是最常用和最有優(yōu)化價(jià)值的。
利用上面的性質(zhì)都可以很容易地把前n個(gè)用O(n)時(shí)間推出來(lái).
當(dāng)然，利用這個(gè)性質(zhì)還可以對(duì)其他積性函數(shù)進(jìn)行優(yōu)化，這里僅介紹兩個(gè)常用和有優(yōu)化價(jià)值的。
1)歐拉函數(shù)(phi)
傳統(tǒng)的算法:
對(duì)于某素?cái)?shù)p且n|p(n能整除p)
if( (n/p) % i == 0 ) phi(n)=phi(n/p)*i;
else phi(n)=phi(n/p)*(i-1);
這個(gè)傳統(tǒng)算法的性質(zhì)正好用在篩素?cái)?shù)算法中.
p為n的最小素因子,當(dāng)n/p包含該因子p,則phi(n)=phi(n/p)*i;否則phi(n)=phi(n/p)*(i-1);
p即pr[j], n/p即i, n即i*pr[j]了.
2)約數(shù)個(gè)數(shù)(divnum)
約數(shù)不能像phi那么自然,但還是有不錯(cuò)的方法.
約數(shù)個(gè)數(shù)有個(gè)性質(zhì)
divnum(n)=(e1+1)*(e2+1)...(ei表示n的第i個(gè)質(zhì)因數(shù)的個(gè)數(shù).)
傳統(tǒng)方法就是對(duì)每個(gè)數(shù)分解質(zhì)因數(shù),獲得各因數(shù)個(gè)數(shù)再用上式.
開(kāi)一個(gè)空間e[i]表示最小素因子的次數(shù)
這次說(shuō)直接點(diǎn):
篩到i 第j個(gè)素?cái)?shù)
對(duì)于divnum
如果i|pr[j] 那么 divnum[i*pr[j]]=divsum[i]/(e[i]+1)*(e[i]+2) //最小素因子次數(shù)加1
否則 divnum[i*pr[j]]=divnum[i]*divnum[pr[j]] //滿足積性函數(shù)條件
對(duì)于e
如果i|pr[j] e[i*pr[j]]=e[i]+1; //最小素因子次數(shù)加1
否則 e[i*pr[j]]=1; //pr[j]為1次
轉(zhuǎn)自：
http://hi.baidu.com/cjhh314/blog/item/bfe13bce20fb7c3db600c85c.html