该模板来自于吉林大学ACM模板库
#include<iostream>
using namespace std;
const int base = 10000;
const int width = 4;
const int N = 1000;
struct bint{
int ln,v[N];
bint(int r=0){
for(ln = 0;r>0;r/=base)v[ln++] = r%base;
}
bint operator = (const bint &r){
memcpy(this,&r,(r.ln+1)*sizeof(int));
return *this;
}
};
bool operator < (const bint &a,const bint &b){
int i;
if(a.ln!=b.ln)return a.ln<b.ln;
for(i=a.ln-1;i>=0&&a.v[i]==b.v[i];i--);
return i<0?0:a.v[i]<b.v[i];
}
bool operator <= (const bint& a,const bint& b){
return !(b<a);
}
bint operator + (const bint &a, const bint &b){
bint res;int i,cy=0;
for(i=0;i<a.ln||i<b.ln||cy>0;i++){
if(i<a.ln)cy+=a.v[i];
if(i<b.ln)cy+=b.v[i];
res.v[i] = cy%base; cy/=base;
}
res.ln = i;
return res;
}
bint operator - (const bint &a,const bint &b){
bint res;int i,cy=0;
for(res.ln=a.ln,i=0;i<res.ln;i++){
res.v[i] = a.v[i]-cy;
if(i<b.ln)res.v[i]-=b.v[i];
if(res.v[i]<0)cy=1,res.v[i]+=base;
else cy = 0;
}
while(res.ln>0&&res.v[res.ln-1]==0)res.ln--;
return res;
}
bint operator * (const bint &a,const bint &b){
bint res;res.ln = 0;
if(0==b.ln){res.v[0]=0;return res;}
int i,j,cy;
for(i=0;i<a.ln;i++){
for(j=cy=0;j<b.ln||cy>0;j++,cy/=base){
if(j<b.ln)cy+=a.v[i]*b.v[j];
if(i+j<res.ln)cy+=res.v[i+j];
if(i+j>=res.ln)res.v[res.ln++] = cy%base;
else res.v[i+j] = cy%base;
}
}
return res;
}
bint operator / (const bint &a,const bint &b){
bint tmp,mod,res;
int i,lf,rg,mid;
mod.v[0] = mod.ln = 0;
for(i=a.ln-1;i>=0;i--){
mod = mod*base+a.v[i];
for(lf=0,rg=base-1;lf<rg;){
mid = (lf+rg+1)/2;
if(b*mid<=mod)lf=mid;
else rg = mid-1;
}
res.v[i] = lf;
mod = mod-b*lf;
}
res.ln = a.ln;
while(res.ln>0&&res.v[res.ln-1]==0)res.ln--;
return res;
}
bint operator % (const bint &a,const bint &b){
bint tmp,mod,res;
int i,lf,rg,mid;
mod.v[0] = mod.ln = 0;
for(i=a.ln-1;i>=0;i--){
mod = mod*base+a.v[i];
for(lf=0,rg=base-1;lf<rg;){
mid = (lf+rg+1)/2;
if(b*mid<=mod)lf=mid;
else rg = mid-1;
}
res.v[i] = lf;
mod = mod-b*lf;
}
res.ln = a.ln;
while(res.ln>0&&res.v[res.ln-1]==0)res.ln--;
return mod;
}
int digits(bint &a){
if(a.ln==0)return 0;
int l = (a.ln-1)*4;
for(int t=a.v[a.ln-1];t;++l,t/=10);
return l;
}
bool read(bint &b,char buf[]){
if(1!=scanf("%s",buf))return 0;
int w,u,ln = strlen(buf);
memset(&b,0,sizeof(bint));
if('0'==buf[0]&&0==buf[1])return 1;
for(w=1,u=0;ln;){
u += (buf[--ln]-'0')*w;
if(w*10==base){
b.v[b.ln++] = u;
u = 0;
w = 1;
}else{
w *=10;
}
}
if(w!=1)b.v[b.ln++]=u;
return 1;
}
void write(const bint &v){
int i;
printf("%d",v.ln==0?0:v.v[v.ln-1]);
for(i=v.ln-2;i>=0;i--){
printf("%04d",v.v[i]);
}
printf("\n");
}
int main(){
bint a,b,c;char buf[100];
read(a,buf);b=a-1;
write((a%b));
return 0;
}
分享到:
相关推荐
c++大数模板 内含各种大数操作 还可以自己设置数的长度
用C++写的重载的大数模板 大数加法、大数乘法、大数除法、大数减法 带有注释
这是一个通用的大数模板,是用C++编的,当需要进行大数运算时可以直接套用!!
处理大数的模板,C++大数模板。ACM必备
还在为ACM的大数高精度困扰吗?赶快用java的大数类吧!
ACM中的常用高精度模板,内容:大数加法,大数乘小数,大数乘大数,大数除法。
包含C++高精度大数的两份模板,一份简便,一份详细的。
N进制大数相减,大数比较,大数乘法,大数乘浮点数(支持大数乘大数),大数阶乘,大数相加,大数相减(负数结果带符号),大数相减,大数之差(绝对值),浮点大数求幂(支持整数大数求幂),整数大数求幂
使用最通俗的语言写的高精度模板,适合初学者,效率不低。
原来令人纠结的大数问题 用java处理起来那么容易 汗
ACM大数模版ACM大数模版ACM大数模版ACM大数模版ACM大数模版ACM大数模版ACM大数模版ACM大数模版
大数的加减乘除,C++,C语言
本篇文章是对C++大数模板的程序代码进行了详细的分析介绍,需要的朋友参考下
帮助初学者处理acm中的常见大数问题! 其中一些模板值得参考!!!
大数模板,字符读入 四. 数论算法 1. Greatest Common Divisor最大公约数 2. Prime素数判断 3. Sieve Prime素数筛法 4. Module Inverse模逆元 5. Extended Euclid扩展欧几里德算法 6. Modular Linear Equation模...
很好的体现大数模板在各种应用中的不可思议的作用。
大数模板,字符读入 数论算法 1. Greatest Common Divisor最大公约数 2. Prime素数判断 3. Sieve Prime素数筛法 4. Module Inverse模逆元 5. Extended Euclid扩展欧几里德算法 6. Modular Linear Equation模线性...
我测试通过的大数计算模板,遇到一些简单题可以直接代入
一. 常用函数与STL 二. 重要公式与定理 三. 大数模板 四. 数论算法 五. 图论算法 六. 几何算法 七. 专题讨论
包括常用函数与STL 大数模板,字符读入 数论算法 图论算法 几何算法等