blob: 1db07632b391f5c39aebd5d583e4e53656d0297e (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
#include <cassert>
#include "numalgo.h"
using namespace std;
Bigint gcd(Bigint a,Bigint b){
while(true){
if(a==0)return b;
if(b==0)return a;
if(a>=b)a=a.divmod(b).second;
else b=b.divmod(a).second;
}
}
Bigint egcd(const Bigint &a,const Bigint &b,Bigint &x,Bigint &y){
Bigint x2(0),y2(1),r(a),r2(b);
x=1; y=0;
//cerr<<x<<"\t * "<<a<<"\t + "<<y<<"\t * "<<b<<"\t = "<<r<<endl;
while(r2!=0){
pair<Bigint,Bigint> dm=r.divmod(r2);
//cerr<<x2<<"\t * "<<a<<"\t + "<<y2<<"\t * "<<b<<"\t = "<<r2<<" (q = "<<dm.first<<')'<<endl;
Bigint xn=x-dm.first*x2;
Bigint yn=y-dm.first*y2;
x=x2; x2=xn;
y=y2; y2=yn;
r=r2; r2=dm.second;
}
return r;
}
Bigint expmod(const Bigint &b,const Bigint &e,const Bigint &m){
assert(e>=0);
assert(m>=1);
if(m==1)return Bigint(0);
Bigint res(1);
vector<bool> bits(e.bits());
for(int i=bits.size()-1;i>=0;i--){
res*=res;
if(bits[i])res*=b;
res=res.divmod(m).second;
}
return res;
}
int ilog2(uint64_t i){
assert(i);
int l=0;
while(i>>=1)l++;
return l;
}
|
