寫這篇文章，可謂是頗費了些周折，其實這篇文章早在３個星期以前就可以發了，一篇３０００多字的文章，由于一次死機，數據丟失而不得不重寫．第二次寫了一部分的時候干脆機器整個崩潰，無法開機，直接報修去了．這是３次動筆，三次思考得到的文章，我想，這次寫的東西可能會和第一第二次的內容略有不同，但是這不會影響問題的本質，只不過換了個表現形式罷了．
不知道為什么，我突然想起了王勃著名的＜滕王閣序＞：＂時運不濟， 命運多舛。 馮唐易老， 李廣難封。 屈賈誼于長沙， 非無圣主； 竄梁鴻于海曲， 豈乏明時。所賴君子見機，達人知命"．以前讀到這幾句，只覺他文筆好，卻未得其中深意，今天再度回首，終于能夠得以品匝出其中的苦澀厚味了．時運不濟，命運多舛啊..．昔日賈誼被扁長沙，并非沒有明主（漢文帝），而梁鴻來到海曲，也并非是世道暗無天日之時（其實覺得賈誼用這個典故來抒懷比較牽強:-P）。今天我們有明主明時，他它叫做“實力”，但是我們卻沒能逃過賈梁二人的結局，實在是令人扼腕嘆息。不過那又能說明什么呢,魚頭有言，命運決定于你對待問題的態度，而不是結果，為什么我們又不能做到“窮且益堅，不墜青云之志。酌貪泉而覺爽，處涸轍以猶歡。北海雖賒，扶搖可接；東隅已逝，桑榆非晚。孟嘗高潔，空懷報國之心；阮藉猖狂，豈效窮途之哭？”呢？，我們應該善于抓住問題的本質，而不是區區一個結果。我必須承認，這次的結局是不盡人意的，這讓我們錯失了一個非常珍貴的機會（我相信這樣的機會不會太多），也沒有給魚頭一個滿意的答復，這個我是需要付絕對責任的。但是客觀地來看，勝敗乃兵家常事，有得有失，自然之理，有的人表面上成功了，其實他未必真具實力，而有些人表面上失敗了，但是也不見得此人沒有真才實學。我想，這都是正?，F象，只是不正常的地方在于，有的人抓住了一次機遇，就沾沾自喜，而另一些人結局杯具，就從此一蹶不振，殊不知，有的時候，只是機遇的天平倒向了另一側罷了。所以，對于把握住機遇的人，應該認真總結，彌補自己的不足，再接再礪，而對于失敗者，更應該吸取教訓與不足，讓自己的成功成為必然。所以，沒有絕對的成功者或是失敗者，We are all the same~ 我不想以失敗者的角度來寫這篇總結，原因上面已經解釋得較為清楚，故不在贅述。
對于這次比賽，我們隊三個隊員的態度都是非常認真的，從組隊的那一刻開始，我們便針對將要來到的比賽做了較為細致的準備。暑假回家以后，我們隊組織了三場練習比賽，通過這三次比賽，我們隊伍的合作能力得到了提高。我想，每一個隊員都把接下來的regional比賽看成是自己的頭等大事，我記得甚至在國慶放假的時候，我們都沒有忘記去POJ上練習，我記得我和阿義曾經花了一整天的時間研究出圓和三角形的相交面積，我覺得這樣的態度是值得肯定的。然后便是五場網絡賽，在這幾場比賽中，我們不僅為集訓隊貢獻了題目，而且也起到了鍛煉隊伍的作用。在這幾場比賽中，我們基本上能夠出三道以上的題目(當然有很多題是因為被人先過掉所以就沒做了），我們應該相信，我們在regional的比賽中是能夠獲得滿意成績的。
然后便是上海之行了，作為第一次參加比賽的隊伍，我們的不確定因素有很多，多次比賽的經驗告訴我，他們不容易找到自己在整體中的位置，如果發揮得好，即使將王者趕下王座也不是不可能的。但若是狀態不好，可能結局也會比其他隊伍更糟糕一些。第一次參賽，可謂實力與運氣并存，只是運氣成分的比重稍微大一些吧。當然，如果有事先鍛煉的機會，我想我是絕對會抓住的，哪怕只是一次現場賽的經歷，因為好的心態是靠現場比賽積累出來的，可惜的是，竟然連一次這樣的機會也沒有。就好像是被抓來的壯丁被直接拉上了戰場一樣，槍都端不穩，又如何打仗？
無論如何，我們還是在那個時間，那個地點，出現在了東華的體育場內?？諝庠谶@個體育館里開始凝固，感覺有點令人窒息。題目發下來之后，我看了前四題，華仔看中間3題，阿義看最后三題，我覺得我最大的失誤在于跳過了第一題，因為這個題讓人感覺是個比較難做的計算幾何題，和大家商量了一下之后，我決定跳過。。。然后看了第二題，第二題題目意思比較明白，就是求一個菲薄拉起數列，加一個A^Bmod c的操作，不過關鍵在于參數的值非常大。這個時候，張俊華發現后面的題沒有什么想法，于是回過頭來看第一題，看完之后，覺得這個題應該屬于簡單題，然后就開始敲了，但是交上去,Wa了。這個時候 已經陸陸續續升起了幾只黃色氣球，全場還是單色。所以我的感覺是這題一定是大家都能過的簡單題，大家商量了一下，這個題應該是最好過的，于是華仔和阿義繼續找錯，我看其他的題目。不過近一個小時過去了，依然還是Wa。這個結果令人匪夷所思，難道此題有trick么？我不得不回身看了A題，抓住了幾個易錯點，首先是1的對立狀態不一定是0，其次k還可以等于3.在這兩個地方，我們的程序都沒有考慮到。。。我想大家可能有些緊張了，唯一的辦法是快速AC這道題，才能緩解大家的緊張情緒。我想了想，直接枚舉邊不是更好么？復雜度只有64*64*64,雖然不愿意看到這樣的情況，但是我還是重寫了這道題，交上去，竟然是TLE!在此同時，我們嘗試暴力做了B題，還有那道最小生成樹的題，但都沒有AC,對于A題，雖然我盡量保持冷靜，再想各種各樣的剪枝，但是事后的情況告訴我，我還是遺漏掉一個細節，就是只有不同的狀態之間才可以交換，如果加上這個，可以剪去很多的時間。但我也沒有看到這處用下劃線標記的句子，在這一點上，我需要對全隊負責。
如果可以抉擇的話，我寧愿將這樣的失利，放在省賽或者是邀請賽中，如果要用亞洲區決賽來積累經驗，這個代價未免太大了一些。只能說，我們實在是大手筆了一次 呵呵^_^
賽后，我認真的思考了這次的比賽，我覺得，大家的努力是值得肯定的。但是還有一些主觀和客觀因素制約著我們，我們的不足還有許多。我們參加的比賽比較少，經驗積累得少，這個無疑是很重要的一點。所以我們要抓住各種比賽的機會，主動鍛煉自己的臨場狀態，這樣才能將自己的真正的實力轉化成為AC。
正如我前幾段里說的那樣，一次成敗不足以論英雄，我們要不斷的完善自己，贏得主動，而不是總等待著RP的爆發。呵呵，我突然想起了潤之兄在長征時寫的三首十六字令：
山，快馬加鞭未下鞍。驚回首，離天三尺三?！ ?
山，倒海翻江卷巨瀾。奔騰急，萬馬戰猶酣。
山，刺破青天鍔（è）未殘。天欲墮，賴以拄其間。
在比賽中，我們需要這樣的大氣，需要這樣戰勝一切的信心和魄力，即使“天欲墮”，也要“賴以拄其間”！
（ 這篇文章寫得有些長了，但愿大家還沒有視覺疲勞）今天我所說的一切，只是針對一次的比賽，要知道，事情是不短變化發展中的，今天的經驗只能屬于過去，我們需要做的是用這有限的經驗去適應無限變化的環境。所謂態度決定一切，我相信，通過我們的努力，大家終會有“更喜岷山千里雪，三軍過后盡開顏"的一天！
By abilitytao
2009年11月28日夜
后來居然卡了一道2-sat，原來是將n寫成了m,小錯誤總是不停的犯，也該到頭了吧～
6道2-sat題號
> 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
如果一開始我也用兩個dp數組就好了，但是我錯誤地認為如果從后往前掃描數組的話是不會出現相互影響的情況的，事實上我錯了，原來數據里有重量為0的數據，如果有一對寶藏他們有兩種取法（如第二種情況）而這兩件寶物的重量又恰好為0，那么用 dp[j]=dp[j-w]+v[i] 這個狀態轉移方程相當于兩件寶物都取了，這違背了題意，除了這一種情況之外，其他的情況都可以直接用上面的轉移方程式（所以說這個題真的很猥瑣，但也體現出我對背包問題掌握的不全面）。
當我知道了這個陷阱后，我極力的想證明只有都是0的情況才不能用上面的方法，所以我只開了一個dp數組，事實上證明我是正確的！這個題糾結了較長時間，雖然能比當場做出來的同學想的更清晰，但是總是現場卡題也不是個好現象，有則改之吧。
#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 又快到了，希望自己能正常發揮，不過這次是DIV 1了，希望題目不要太難 ，呵呵 加油啦 ^_^
這次的月賽暴露了我很多不足 在活動室待了5個小時 腦子一片空白，思維非常僵硬 做了個搜索題 卡了，再做個DP題，還卡 ，做圖論考慮復雜度的時候不敢用暴力，結果沒編完，那個匹配是真的沒想到，這是唯一可以商榷的題目。在活動室做題可能不太習慣吧，鬧哄哄的，靜不下心來，而且我最近還缺少做題的魄力，一夫當關萬夫莫開的魄力。魚頭旁觀者清，說的沒錯，時不我待，是該有所改變的時候了。
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
|
|
|
|
求哈密頓通路的數目，題目中指定了一些道路必須經過。
1。做法是求連通分支，縮點，并判斷有沒有出現環或者非正常情況，若出現直接返回0。
2。求連通分支數的全排列；
3。遍歷所有連通分支
4。如果該連通分支擁有的點數>=2,則結果乘以2，即可得到答案.
求的時候要注意mod操作，要用long long 保存中間數據，(a*b)mod c中 a*b可能溢出32位整數。
#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,寫的不好還請大家多多指點 :-)
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
這個文章主要介紹了3算法
1線性時間篩素數
2線性時間求前n個數的歐拉函數值
3線性時間求前n個數的約數個數
一、 首先介紹下積性函數。
下面是wiki的條目：
在非數論的領域，積性函數指有對于任何a,b都有性質f(ab)=f(a)f(b)的函數。
在數論中的積性函數。對于正整數n的一個算術函數f(n)，當中f(1)=1且當a,b互質，f(ab)=f(a)f(b)，在數論上就稱它為積性函數。
若某算術函數f(n)符合f(1)=1，且就算a,b不互質，f(ab)=f(a)f(b)，稱它為完全積性的。
例子
φ(n) －歐拉φ函數，計算與n互質的正整數之數目
μ(n) －默比烏斯函數，關于非平方數的質因子數目
gcd(n,k) －最大公因子，當k固定的情況
d(n) －n的正因子數目
σ(n) －n的所有正因子之和
σk(n): 因子函數，n的所有正因子的k次冪之和，當中k可為任何復數。在特例中有：
σ0(n) = d(n) 及
σ1(n) = σ(n)
1(n) －不變的函數，定義為 1(n)=1 （完全積性）
Id(n) －單位函數，定義為 Id(n)=n （完全積性）
Idk(n) －冪函數，對于任何復數、實數k，定義為Idk(n) = nk （完全積性）
Id0(n) = 1(n) 及
Id1(n) = Id(n)
ε(n) －定義為：若n = 1，ε(n)=1；若n > 1，ε(n)=0。有時稱為“對于狄利克雷回旋的乘法單位”（完全積性）
(n/p) －勒讓德符號，p是固定質數（完全積性）
λ(n) －劉維爾函數，關于能整除n的質因子的數目
γ(n)，定義為γ(n)=(-1)ω(n)，在此加性函數ω(n)是不同能整除n的質數的數目
所有狄利克雷特性均是完全積性的
二、再介紹下線性篩素數方法
bool notp[mr];//素數判定
__int64 pr[670000],pn,ans;//pr存放素數,pn當前素數個數。
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;
}
}
}
利用了每個合數必有一個最小素因子。
每個合數僅被它的最小素因子篩去正好一次。所以為線性時間。
代碼中體現在：
if(i%pr[j]==0)break;
pr數組中的素數是遞增的,當i能整除pr[j]，那么i*pr[j+1]這個合數肯定被pr[j]乘以某個數篩掉。
因為i中含有pr[j],pr[j]比pr[j+1]小。接下去的素數同理。所以不用篩下去了。
在滿足i%pr[j]==0這個條件之前以及第一次滿足改條件時,pr[j]必定是pr[j]*i的最小因子。
三、結合線性篩素數算法的優化算法
基于這個線性篩素數算法,我們可以很容易地得到某個數的最小素因子。
因為當i%pr[j]!=0的時候,最小素因子pr[j]與i互質,滿足積性函數的條件,可以直接得到f(i*pr[j])=f(i)*f(pr[j]).
不過當i%pr[j]==0時我們必須根據該積性函數本身的特性進行計算.或者在篩的同時保存并遞推些附加信息.總之要O(1)求得f(i*pr[j])及完成遞推附加信息.
下面的兩個例子是歐拉函數phi和約數個數.這兩個是最常用和最有優化價值的。
利用上面的性質都可以很容易地把前n個用O(n)時間推出來.
當然，利用這個性質還可以對其他積性函數進行優化，這里僅介紹兩個常用和有優化價值的。
1)歐拉函數(phi)
傳統的算法:
對于某素數p且n|p(n能整除p)
if( (n/p) % i == 0 ) phi(n)=phi(n/p)*i;
else phi(n)=phi(n/p)*(i-1);
這個傳統算法的性質正好用在篩素數算法中.
p為n的最小素因子,當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)約數個數(divnum)
約數不能像phi那么自然,但還是有不錯的方法.
約數個數有個性質
divnum(n)=(e1+1)*(e2+1)...(ei表示n的第i個質因數的個數.)
傳統方法就是對每個數分解質因數,獲得各因數個數再用上式.
開一個空間e[i]表示最小素因子的次數
這次說直接點:
篩到i 第j個素數
對于divnum
如果i|pr[j] 那么 divnum[i*pr[j]]=divsum[i]/(e[i]+1)*(e[i]+2) //最小素因子次數加1
否則 divnum[i*pr[j]]=divnum[i]*divnum[pr[j]] //滿足積性函數條件
對于e
如果i|pr[j] e[i*pr[j]]=e[i]+1; //最小素因子次數加1
否則 e[i*pr[j]]=1; //pr[j]為1次
轉自：
http://hi.baidu.com/cjhh314/blog/item/bfe13bce20fb7c3db600c85c.html