比赛 201712练习 评测结果 AAAAAAAAAA
题目名称 大整数取模 最终得分 100
用户昵称 胡嘉兴 运行时间 0.005 s
代码语言 C++ 内存使用 0.31 MiB
提交时间 2017-12-25 18:54:30
显示代码纯文本
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<stack>
#include<cstdio>
#define ll long long
using namespace std;
const ll maxn=15007;
typedef struct Bigint{
	ll a[maxn];
	void Init(string s){//赋值
		memset(a,0,sizeof(a));
		a[0]=s.size();
		for(ll i=1;i<=a[0];i++)a[i]=s[a[0]-i]-'0';
		while(a[0]>1 && a[a[0]]==0)a[0]--;
	}
	void init(ll temp){
	    memset(a,0,sizeof(a));
	    a[0]=1;
		a[1]=temp;
	}
	Bigint operator + (const Bigint & b)const{//高精加高精
		Bigint c;memset(c.a,0,sizeof(c.a));
		c.a[0]=max(a[0],b.a[0]);
		for(ll i=1;i<=c.a[0];i++){
			c.a[i]+=a[i]+b.a[i];
			if(c.a[i]>9){
				c.a[i+1]++;
				c.a[i]-=10;
			}
		}
		if(c.a[c.a[0]+1])c.a[0]++;
		return c;
	}
	Bigint operator - (const Bigint & b)const{//高精减高精
		Bigint c;memset(c.a,0,sizeof(c.a));
		c.a[0]=max(a[0],b.a[0]);
		for(ll i=1;i<=c.a[0];i++){
			c.a[i]+=a[i]-b.a[i];
			if(c.a[i]<0){
				c.a[i+1]--;
				c.a[i]+=10;
			}
		}
		while(c.a[0]>1 && c.a[c.a[0]]==0)c.a[0]--;
		return c;
	}
	Bigint operator * (const Bigint & b)const{//高精乘高精
		Bigint c;
		memset(c.a,0,sizeof(c.a));
		c.a[0]=a[0]+b.a[0]-1;
		for (int i = 1; i <= a[0]; i ++){
			int tem = 0;
			for (int j = 1; j <= b.a[0]; j ++){
				tem = a[i] * b.a[j] + tem / 10 + c.a[i + j - 1] ;
				c.a[i + j - 1] = tem % 10;
			}
			if (tem / 10){
				c.a[i + b.a[0]] = tem / 10;
			}
		}
		if(c.a[c.a[0]+1]){
                c.a[0]++;
		}
		while(c.a[0]>1 && c.a[c.a[0]]==0){
                c.a[0]--;
		}
		return c;
	}
	bool operator < (const Bigint & b)const{//重载小于号
		if(a[0]<b.a[0])return true;
		if(a[0]>b.a[0])return false;
		for(ll i=a[0];i;i--){
			if(a[i]>b.a[i])return false;
			if(a[i]<b.a[i])return true;
		}
		return false;
	}
	bool operator == (const Bigint & b)const{//重载等于号
		if(a[0]^b.a[0])return false;
		for(ll i=a[0];i;i--)if(a[i]^b.a[i])return false;
		return true;
	}
	bool operator > (const Bigint & b)const{//重载大于号
		if(a[0]<b.a[0])return false;
		if(a[0]>b.a[0])return true;
		for(ll i=a[0];i;i--){
			if(a[i]>b.a[i])return true;
			if(a[i]<b.a[i])return false;
		}
		return false;
	}
	Bigint operator / (const ll & temp)const{//高精除低精
		Bigint b; memset(b.a,0,sizeof(b.a));
		b.a[0]=a[0];
		ll x=0;
		for(ll i=a[0];i>=1;i--){
			b.a[i]=(x*10+a[i])/temp;
			x=(x*10+a[i])%temp;
		}
		while(b.a[0]>1 && b.a[b.a[0]]==0)b.a[0]--;
		return b;
	}
	Bigint operator * (const ll & temp)const{//高精乘低精
		Bigint b;memset(b.a,0,sizeof(b.a));
		b.a[0]=a[0];
		for(ll i=1;i<=a[0];i++)b.a[i]=a[i]*temp;
		for(ll i=1;i<=b.a[0];i++){
			if(b.a[i]>9){
				b.a[i+1]+=b.a[i]/10;
				b.a[i]%=10;
				if(i==b.a[0])b.a[0]++;
			}
		}
		while(b.a[0]>1 && b.a[b.a[0]]==0)b.a[0]--;
		return b;
	}
	ll operator % (const ll & temp)const{//高精模低精
		ll  date=0;
		for(ll i=a[0];i>=1;i--){
			date=date*10+a[i];
			date%=temp;
		}
		return date;
	}
}BIG;
Bigint numcpy(const Bigint p,ll pos){//从pos开始的地方复制p数组到q数组
	Bigint a;memset(a.a,0,sizeof(a.a));
	for(ll i=1;i<=p.a[0];i++)a.a[i+pos-1]=p.a[i];
	a.a[0]=p.a[0]+pos-1;
	return a;
}
Bigint operator / (Bigint & a,Bigint & b){//高精除高精
	Bigint c;memset(c.a,0,sizeof(c.a));
	if(a==b){c.Init("1");return c;}
	if(a<b){c.Init("0");return c;}
	c.a[0]=a.a[0]-b.a[0]+1;
	for(ll i=c.a[0];i>0;i--){
		Bigint temp=numcpy(b,i);
		while(a>temp || a==temp){c.a[i]++;a=a-temp;}
	}
	while(c.a[0]>1 && c.a[c.a[0]]==0)c.a[0]--;
	return c;
}
Bigint operator % (Bigint & a,Bigint & b){//高精模高精
	Bigint c;memset(c.a,0,sizeof(c.a));
	if(a==b){c.Init("0");return c;}
	if(a<b)return a;
	c.a[0]=a.a[0]-b.a[0]+1;
	for(ll i=c.a[0];i>0;i--){
		Bigint temp=numcpy(b,i);
		while(a>temp || a==temp){
			c.a[i]++;
			a=a-temp;
		}
	}
	return a;
}
Bigint qpow(Bigint a,int k){//高精快速幂
	Bigint ans;
	ans.Init("1");
	while(k){
		if(k&1)
		{
		    ans=ans*a;
		}
		a=a*a;
		k>>=1;
	}
	return ans;
}
Bigint BIG_sqrt()
{
    BIG a,l,r,yi,ans;
	string s;
	cin>>s;
	a.Init(s);
	l.Init("0");
	r.Init(s);
	yi.Init("1");
	while(l<r||l==r){
		BIG mid=l+r;
		mid=mid/2;
		Bigint ans;
		ans=mid*mid;
		if(ans==a)
        {
            return mid;
        }
		if(ans<a)
		{
		    l=mid+yi;
		}
		else
		{
            r=mid-yi;
		}
	}
	return r;
}
int main()
{
    freopen("bigint.in","r",stdin);
    freopen("bigint.out","w",stdout);
    string s;
    BIG n;
    ll m, ans;
    cin>>s>>m;
    n.Init(s);
    cout<<n%m;
    return 0;
}