Initial

1 files changed, 50 insertions, 0 deletions

diff --git a/numalgo.cpp b/numalgo.cpp
new file mode 100644
index 0000000..1db0763
--- /dev/null
+++ b/numalgo.cpp
@@ -0,0 +1,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;
+}