记录编号	221623	评测结果	EEEEEEEEEE
题目名称	取余运算2	最终得分	0
用户昵称	liu_runda	是否通过	未通过
代码语言	C++	运行时间	0.738 s
提交时间	2016-01-24 17:18:00	内存使用	0.58 MiB

#include<cstdio>
#include<iostream>
#define max(a,b) a>b?a:b
using namespace std;
const int base = 1000000;
struct bigint{
	long long data[5000];
	int len;
	bigint(long long _a=0){
		if(_a==0){
			len=0;
			data[0]=0;
			cout<<"aha";
			return;
		}
		data[0]=_a;
		len=0;
		for(;data[len]>=base;++len){
			data[len+1]+=data[len]/base;
			data[len]%=base;
		}
		len++;
	}
	bigint(const bigint& a){
		len = a.len;
		for(int i = 0;i<len;++i)data[i]=a.data[i];
	}
	bool operator == (const bigint &b){
		if(len!=b.len)return false;
		else{
			for(int i = 0;i<len;++i)if(data[i]!=b.data[i])return false;
			return true;
		}
	}
	bigint operator + (const bigint &b){
		const bigint&a = *this;
		bigint c;
		int lim = max(a.len,b.len);
		for(int i = 0;i<lim;++i)c.data[i]=a.data[i]+b.data[i];
		for(int i = 0;i<lim;++i){
			c.data[i+1]+=c.data[i]/base;
			c.data[i]%=base;
		}
		if(c.data[lim]!=0){
			c.len = lim+1;
		}else{
			c.len = lim;
		}
	}
	bigint operator * (const bigint &b){
		const bigint &a = *this;
		int lim = a.len+b.len-1;
		bigint c;
		int d;
		for(int i = 0;i<a.len;++i){
			for(int j = 0;j<b.len;++j){
				d = i+j;
				c.data[d] += a.data[i]*b.data[j];
				if(c.data[d]>=base){
					c.data[d+1]+=c.data[d]/base;
					c.data[d]%=base;
				}
			}
		}
		if(c.data[lim]!=0){
			c.len = lim+1;
		}
		else{
			c.len = lim;
		}
		return c;
	}
	bigint operator%(const bigint &x){
		bigint c(*this);//复制一份除数
		if(c.len==1&&x.len==1){
			cout<<data[0]<<endl<<x.data[0]<<endl;
			cout<<"=="<<data[0]%x.data[0]<<endl;
			return bigint(data[0]%x.data[0]);
		}
		else if(x.len==1){
			int y = x.data[0];
			for(int i = c.len-1;i>0;--i){
				c.data[i]%=y;
				c.data[i-1] += c.data[i]*base;
			}
			c.data[0]%=y;
			return bigint(c.data[0]);
		}
		else{
		}
	}
	bigint operator%(int x){
		return (*this)%bigint(x);
	}
	bigint half(){//(*this)/2,floor
		if(len<=1)return bigint(data[0]/2);
	}
	
};      
ostream& operator <<(ostream &out,const bigint& a){
	printf("%d",a.data[a.len-1]);
	for(int i = a.len-2;i>=0;--i){
		printf("%04d",a.data[i]);
	}
	printf("\n");
	return out;
}
bigint n,k;
bigint result(bigint m){//n^m %k n<k
	printf("aha:");
	if(m.len == 0)return bigint(1);//n^0==1
	else if(m == 1){
		printf("second\n");
		return n%k;//n^1 == n
	}else if(m%1==1){//n^(2i+1) %k = (n^i %k)^2 *n %k
		bigint r = result(m.half());
		r = r*r;
		r = r%k;
		r = r*n;
		r = r%k;
		return r;
	}else{//n^(2i)%k = (n^i %k)^2 %k;
		bigint r = result(m.half());
		r = r*r;
		r = r%k;
		return r;
	}
}
int main(){
//	freopen("helpless.in","r",stdin);
//	freopen("helpless.out","w",stdout);
	long long _n,_m,_k;
	cin>>_n>>_m>>_k;
	cout<<bigint(_n)<<bigint(_m)<<bigint(_k);
	cout<<((bigint(_n)*bigint(_m))%bigint(_k));
	cout<<_n*_m%_k<<endl;
/*	_n=_n%_k;
	n = bigint(_n);
	bigint m(_m);
	m = bigint(_m);
	cout<<result(m);*/
//	fclose(stdin);fclose(stdout);
	return 0;
}