 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
随机算法就是这样的啦，有一点点的问题就挂了In Reply To:Pollard部分，怎么可能有死循环哦？！ Posted by:queyue2004 at 2005-07-09 22:11:29 >
> __int64 PollardRho (const __int64 &c,const __int64 &test)
> {
> __int64 y,x,gcd;
> int i,k;
>
> y = x = rand () % test;
> i = 1;
> k = 2;
> do
> {
> i++;
> gcd = Gcd (2 * test + y - x,test);
> if (gcd > 1 && gcd < test)
> {
> return gcd;
> }
> if (i == k)
> {
> y = x;
> k *= 2;
> }
> x = (x * x + test - c) % test;
> }while (x != y);
>
> return test;
> }
>
> //----------------------------------------------
>
> //----------------------------------------------
> void Rho (const __int64 &test)
> {
> __int64 n;
>
> if (MillerRabin (test,2))
> {
> if (test < min)
> {
> min = test;
> }
> }
> else
> {
> n = PollardRho (rand() % (test - 1) + 1,test);
> if (n < test)
> {
> Rho (n);
> Rho (test / n);
> }
> }
> }
Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
