比赛 |
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;
}