#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;
}