[algogeeks] Fact1 spoj

[navin]

Hi,

I implemented pollard rho to find factors .
In Fact1 they given 20 digits largest 20 digits number is
99999999999999999999 (20 9s).
But largest 64 bit no is 18446744073709551615 .
My algo fails in this case.

I searched one person solved this problem in c++ code got AC.
https://www.spoj.pl/status/FACT1/
if there exists another algorithm please tell me.
so kindly help me.

here follows my code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
#define LET(x,a) typeof(a) x(a)
#define FOR(i,a,b) for(LET(i,a);i < (b);++i)
#define FORZ(i,n) FOR(i,0,n)
#define dbge(x) cout << #x << " -> " << x << "\t" << endl;

typedef unsigned long long LL;
LL mx = 18446744073709551615llu;

LL mul(LL a, LL b, LL mod)
{
   if(mx/a >= b)
       return a*b % mod;
   int i = 63;
   for(;i >= 0;--i)
       if(b & (1ll << i))
           break;
   LL ans = 0;
   for(; i >= 0; --i)
   {
       ans = 2*ans%mod;
       if(b & (1ll << i))
           ans = (ans + a)%mod;
   }
   return ans;
}

LL mypow(LL a, LL b, LL mod)
{
   if(b == 0)
       return 1 % mod;
   if(b & 1)
       return mul(mypow(a,b - 1, mod),a, mod);
   LL x = mypow(a, b / 2, mod);
   return mul(x,x, mod);
}

LL gcd(LL a,LL b)
{
        if (a%b==0) return b;
        else
        return gcd(b,a%b);
}

LL miller(LL a)
{

       LL p = __builtin_ctz(a - 1);
       LL val = (a - 1) >> p;
       bool f = 0;

       if(a > 3 && a % 6 != 1 && a % 6 != 5)
           f = 1;
       if(!f)
       FORZ(i,1)
       {
           LL x = rand() % a;
           if(x == 0)
               x++;
           LL foo = mypow(x, val,a);

           FORZ(i,p)
           {
               LL y = mul(foo, foo, a);
               if(y == 1 && foo != 1 && foo != a - 1)
               {
                   f = 1;
                   break;
               }
               foo = y;
           }
           if(foo != 1)
           {
               f = 1;
               break;
           }
       }
       if(!f)
       {
           return 1;
         //  printf("YES\n");
       }
       else
       {
           return 0;
           //printf("NO\n");
       }

}

int pollardrho( int n )
{
        if ( n%2 == 0 )
         return 2;
        srand( 2 );
        LL x = rand()%18446744073709551615llu;
        LL c = rand()%18446744073709551615llu;
        LL y = x;
        LL d = 1;

        while( d == 1 )
        {
            x = mul(x, x, n);
            x = (x+c) % n;

            y = mul(y, y, n);
            y = (y+c) % n;

            y = mul(y, y, n);
            y = (y+c) % n;

            d=gcd(x-y,n);

            if( d == n )
                break;
        }

        return d;
}

vector < LL > factor( LL n )
{
        queue<LL> q;
        q.push( n );
        vector<LL> ans;
        while( ! q.empty() )
        {
                LL l = q.front();
                q.pop();
                if( miller(l) )
                {
                        ans.push_back( l );
                        continue;
                }
                LL d = pollardrho( l );
                dbge(d);
                dbge(l);
                if ( d == l ) q.push( d );
                else
                {
                        q.push( d );
                        q.push( l/d );
                }
        }
        return ans;
}

main()
{
        while(1)
        {

        LL n;
        if ( ! n ) break;
        cin >> n;

        vector<LL> v = factor(n);

        map<LL,int> mp;

        for(int i = 0 ; i < v.size() ; i ++ )
        {
                mp[ v[i] ] ++;
//              cout << v[i] <<" ";
        }

        for(map<LL,int>::iterator it = mp.begin() ; it != mp.end(); it++ )
        cout << it->first <<"^"<<it->second<<" ";
        cout << endl ;

        }
}

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.