写这篇文章，可谓是颇费了些周折，其实这篇文章早在３个星期以前就可以发了，一篇３０００多字的文章，由于一次死机，数据丢失而不得不重写．第二次写了一部分的时候干脆机器整个崩溃，无法开机，直接报修去了．这是３次动笔，三次思考得到的文章，我想，这次写的东西可能会和第一第二次的内容略有不同，但是这不会影响问题的本质，只不过换了个表现形式罢了．
不知道为什么，我突然想起了王勃著名的＜滕王閣序＞：＂时运不济， 命运多舛。 冯唐易老， 李广难封。 屈贾谊于长沙， 非无圣主； 窜梁鸿于海曲， 岂乏明时。所赖君子见机，达人知命"．以前读到这几句，只觉他文笔好，却未得其中深意，今天再度回首，终于能够得以品匝出其中的苦涩厚味了．时运不济，命运多舛啊..．昔日贾谊被扁长沙，并非没有明主（汉文帝），而梁鸿来到海曲，也并非是世道暗无天日之时（其实觉得贾谊用这个典故来抒怀比较牵强:-P）。今天我们有明主明时，他它叫做“实力”，但是我们却没能逃过贾梁二人的结局，实在是令人扼腕叹息。不过那又能说明什么呢,鱼头有言，命运决定于你对待问题的态度，而不是结果，为什么我们又不能做到“穷且益坚，不坠青云之志。酌贪泉而觉爽，处涸辙以犹欢。北海虽赊，扶摇可接；东隅已逝，桑榆非晚。孟尝高洁，空怀报国之心；阮藉猖狂，岂效穷途之哭？”呢？，我们应该善于抓住问题的本质，而不是区区一个结果。我必须承认，这次的结局是不尽人意的，这让我们错失了一个非常珍贵的机会（我相信这样的机会不会太多），也没有给鱼头一个满意的答复，这个我是需要付绝对责任的。但是客观地来看，胜败乃兵家常事，有得有失，自然之理，有的人表面上成功了，其实他未必真具实力，而有些人表面上失败了，但是也不见得此人没有真才实学。我想，这都是正常现象，只是不正常的地方在于，有的人抓住了一次机遇，就沾沾自喜，而另一些人结局杯具，就从此一蹶不振，殊不知，有的时候，只是机遇的天平倒向了另一侧罢了。所以，对于把握住机遇的人，应该认真总结，弥补自己的不足，再接再砺，而对于失败者，更应该吸取教训与不足，让自己的成功成为必然。所以，没有绝对的成功者或是失败者，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