View Single Post
Old 2011-04-26, 13:14   #27
Xitami
 
Apr 2010

2×7 Posts
Default

Quote:
Originally Posted by zerothbase View Post
[...]This is definitely the weakest part of the entire code.[...]
Code:
Code:
typedef unsigned long long int u64;

inline u64 mulmod(u64 i, u64 j, u64 k){
        u64 p, r = 0;
        while(j > 0){
                if(j&1) //  r = (i + r) % k
                        if(0==r) r=i;
                        else {  r=k-r;
                                if(i>=r) r=i-r;
                                else r=k-r+i;}
                // i = (i + i) % k
                if(i>k-i) i=(i-k)+i;
                else i+=i; 
                j>>=1;}
        return r;}
no MOD, no overflow
Xitami is offline   Reply With Quote