1 条题解

  • 0
    @ 2025-8-24 21:32:52

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar Adove
    私者一时，公者千古

    搬运于2025-08-24 21:32:52，当前版本为作者最后更新于2017-11-09 16:22:11，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

    我又回来啦，上回的代码过于冗长而且效率不太好，这次代码简洁了很多，而且倍增优化让代码时空效率优秀了不少。

    高精度压八位，加减乘除板子都在这里，而且允许读入负数，允许修改压位位数siz

    其实相对来说重点在压位不在倍增吧qwq

    去年发过一篇题解，但去年那篇太过冗长，于是今年又写了一遍qwq

    #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN=1e5;
const int siz=8;
const long long MOD=1e8;//1e siz压位需要取的模数

char ch1[MAXN],ch2[MAXN];
bool f1,f2,f;
long long n;
long long a[MAXN>>2],b[MAXN>>2],s[MAXN>>2];
long long cp[MAXN>>2],lt[MAXN>>2],wsd[MAXN>>2];

void write(long long num[]);//输出函数
void clear(long long num[]);//重置函数
void ry(long long num[]);//>>二进制右移
void ly(long long num[]);//<<二进制左移
void cpy(long long num1[],long long num2[]);//复制函数
int cmp(long long num1[],long long num2[]);//比较函数
void pls(long long a[],long long b[]);//plus加法运算
void mnu(long long a[],long long b[]);//minus减法运算
void mul(long long a[],long long b[]);//multiply乘法运算
void div(long long a[],long long b[]);//divided除法运算

void write(long long num[])
{
	if(f) putchar('-'),f=0;
	printf("%lld",num[num[0]]);
	for(int i=num[0]-1;i;--i) printf("%08lld",num[i]);
	puts("");
}

void clear(long long num[])
{
	for(int i=num[0];i;--i) num[i]=0;
	num[0]=1;
}

void ry(long long num[])
{
	for(int i=num[0];i;--i){
		if((num[i]&1)&&i>1) num[i-1]+=MOD;
		num[i]>>=1;
	}if(!num[num[0]]&&num[0]>1) --num[0];
}

void ly(long long num[])
{
	++num[0];
	for(int i=1;i<=num[0];++i){
		num[i]<<=1;
		if(num[i-1]>=MOD) num[i-1]-=MOD,++num[i];
	}if(!num[num[0]]&&num[0]>1) --num[0];
	return;
}

void cpy(long long num1[],long long num2[])
{
	for(int i=num1[0];i>num2[0];--i) num1[i]=0;
	for(int i=0;i<=num2[0];++i) num1[i]=num2[i];
}

int cmp(long long num1[],long long num2[])
{
	if(num1[0]>num2[0]) return 1;
	if(num1[0]<num2[0]) return -1;
	for(int i=num1[0];i;--i){
		if(num1[i]>num2[i]) return 1;
		if(num1[i]<num2[i]) return -1;
	}return 0;
}

void init()
{
	scanf("%s%s",ch1,ch2);
	if(ch1[0]=='-') ch1[0]='0',f1=1;
	if(ch2[0]=='-') ch2[0]='0',f2=1;//对符号的处理
	int l1=strlen(ch1),l2=strlen(ch2);
	for(int i=l1-1;i>=0;i-=siz){
		long long pw=1;++a[0];
		for(int j=i;j>i-siz&&j>=0;--j){
			a[a[0]]+=(ch1[j]^48)*pw;
			pw=(pw<<3)+(pw<<1);
		}
	}for(int i=l2-1;i>=0;i-=siz){
		long long pw=1;++b[0];
		for(int j=i;j>i-siz&&j>=0;--j){
			b[b[0]]+=(ch2[j]^48)*pw;
			pw=(pw<<3)+(pw<<1);
		}
	}return;
}

void pls(long long a[],long long b[])
{
	if(f1^f2){
		if(f1) f1^=1,mnu(b,a),f1^=1;
		if(f2) f2^=1,mnu(a,b),f2^=1;//加负数等效于减正数
		return;
	}if(f1&f2){
		f1=f2=0,f^=1,pls(a,b);
		f1=f2=1;return;
	}clear(s);s[0]=max(a[0],b[0])+1;
	for(int i=1;i<=s[0];++i){
		s[i]+=a[i]+b[i];
		if(s[i]>=MOD) s[i]-=MOD,++s[i+1];
	}if(!s[s[0]]&&s[0]>1) --s[0];
	return;
}

void mnu(long long a[],long long b[])
{
	if(f1^f2){
		if(f1) f1^=1,f^=1,pls(a,b),f1^=1;
		if(f2) f2^=1,pls(a,b),f2^=1;//减负数等效于加正数
		return;
	}if(f1&f2){
		f1=f2=0,mnu(b,a);
		f1=f2=1;return;
	}if(cmp(a,b)==-1){
		f^=1;mnu(b,a);return;
	}clear(s);s[0]=max(a[0],b[0]);
	for(int i=1;i<=s[0];++i){
		s[i]+=a[i]-b[i];
		if(s[i]<0) s[i]+=MOD,--s[i+1];
	}while(!s[s[0]]&&s[0]>1) --s[0];
	return;
}

void mul(long long a[],long long b[])//模拟竖式乘法
{
	if(f1^f2) f^=1;
	clear(s);s[0]=a[0]+b[0];
	for(int i=1;i<=a[0];++i){
		for(int j=1;j<=b[0];++j){
			s[i+j-1]+=a[i]*b[j];
			if(s[i+j-1]>=MOD) s[i+j]+=s[i+j-1]/MOD,s[i+j-1]%=MOD;
		}
	}if(!s[s[0]]&&s[0]>1) --s[0];
	return;
}

void div(long long a[],long long b[])
{
	if(f1^f2){
		if(f1) f1^=1,f^=1,div(a,b),f1^=1;
		if(f2) f2^=1,f^=1,div(a,b),f2^=1;
		return;
	}clear(s);
	clear(cp),cp[1]=1;clear(lt);
	while(cmp(a,b)!=-1) ly(b),ly(cp);//这里试探商的二进制最高位
	while(cp[0]>1||cp[1]){
		if(cmp(a,b)!=-1){
			mnu(a,b),cpy(a,s);
			pls(lt,cp),cpy(lt,s);//倍增减法，算法主体
		}ry(b),ry(cp);
	}cpy(s,lt),cpy(lt,a);//s为商，lt为余数
	return;
}

int main()
{
	init();
	clear(s);
//	pls(a,b);write(s);
//	mnu(a,b);write(s);
//	mul(a,b);write(s);
	div(a,b);write(s);//write(lt);
	return 0;
}

    然后是去年那篇，自己写了十进制左移右移

    #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int mec=1e4;
int c[14001],num,d[14001],s[18002],lt[14001],e[14001],f[14001]={1,1};
bool tc,td;
char a[150001],b[150001];
void sum(int c[],int d[]);
void dec(int c[],int d[]);
void mul(int c[],int d[]);
void div(int c[],int d[]);
int tpow(int n)
{
    int m=10;
    while(--n)
        m*=10;
    return m;
}
void ly(int c[],int n)
{
    int m=n%4;
    n/=4;
    c[0]+=n;
    for(int i=c[0];i>n;--i)
        c[i]=c[i-n];
    for(int i=n;i;--i)
        c[i]=0;
    if(m)
    {
        m=tpow(m);
        for(int i=n+1;i<=c[0];++i)
        {
            c[i]*=m;
            if(c[i-1]>=mec)
            {
                c[i]+=c[i-1]/mec;
                c[i-1]%=mec;
            }
        }
    }
    if(c[c[0]]>=mec)
    {
        c[++c[0]]=c[c[0]-1]/mec;
        c[c[0]-1]%=mec;
    }
    while(c[c[0]]==0&&c[0]) --c[0];
}
void ry(int c[],int n)
{
    int m=n%4;
    n/=4;
    c[0]-=n;
    for(int i=1;i<=c[0];++i)
        c[i]=c[i+n];
    for(int i=c[0]+1;i<=c[0]+n;++i)
        c[i]=0;
    if(m)
    {
        m=tpow(m);
        for(int i=1;i<=c[0];++i)
        {
            c[i]/=m;
            if(c[i]<=mec)
                c[i]+=c[i+1]%m*mec/m;
        }
    }
    if(c[c[0]]>=mec)
    {
        c[++c[0]]=c[c[0]-1]/mec;
        c[c[0]-1]%=mec;
    }
    while(c[c[0]]==0&&c[0]) --c[0];
}
int cmp(int c[],int d[])
{
    if(c[0]<d[0]) return -1;
    else if(c[0]>d[0]) return 1;
    else
    {
        for(int i=c[0];i;--i)
            if(c[i]>d[i]) return 1;
            else if(c[i]<d[i]) return -1;
    }
    return 0;
}
void cpy(int c[],int d[])
{
    for(int i=c[0];i>d[0];--i)
        c[i]=0;
    for(int i=0;i<=d[0];++i)
        c[i]=d[i];
}
void cler(int s[])
{
    for(int i=s[0];i;--i) s[i]=0;
    s[0]=1;
}
void check(int c[])
{
    printf("%d",c[c[0]]);
    for(int i=c[0]-1;i;--i)
        printf("%04d",c[i]);
    puts("");
}
void init()
{
    scanf("%s%s",a,b);
    if(a[0]=='-') tc=1;
    if(b[0]=='-') td=1;
    for(int i=strlen(a)-1;i>=0;--i)
    {
        if(num%4==0&&a[i]!='-')
        {
            c[++c[0]]=a[i]-'0';
            int pw=10;
            for(int j=1;j<4&&i-j>=0&&a[i-j]!='-';++j)
            {
                c[c[0]]+=(a[i-j]-'0')*pw;
                pw*=10;
            }
        }
        ++num;
    }
    num=0;
    for(int i=strlen(b)-1;i>=0;--i)
    {
        if(num%4==0&&b[i]!='-')
        {
            d[++d[0]]=b[i]-'0';
            int pw=10;
            for(int j=1;j<4&&i-j>=0&&b[i-j]!='-';++j)
            {
                d[d[0]]+=(b[i-j]-'0')*pw;
                pw*=10;
            }
        }
        ++num;
    }
}
void write(int s[])
{
    printf("%d",s[s[0]]);
    for(int i=s[0]-1;i;--i)
        printf("%04d",s[i]);
    puts("");
}
void sum(int c[],int d[])
{
    if(tc&&td)
    {
        putchar('-');
        tc=td=0;
    }
    else if(tc)
    {
        tc=0;
        dec(d,c);
        return;
    }
    else if(td)
    {
        td=0;
        dec(c,d);
        return;
    }
    cler(s);
    s[0]=max(c[0],d[0]);
    for(int i=1;i<=s[0];++i)
    {
        s[i]=c[i]+d[i];
        if(i>1&&s[i-1]>=mec)
        {
            s[i]+=s[i-1]/mec;
            s[i-1]%=mec;
        }
    }
    if(s[s[0]]>=mec)
    {
        s[++s[0]]=s[s[0]-1]/mec;
        s[s[0]-1]%=mec;
    }
}
void dec(int c[],int d[])
{
    if(tc&&td)
    {
        td=0;
        dec(d,c);
        return;
    }
    else if(td)
    {
        td=0;
        sum(c,d);
        return;
    }
    else if(tc)
    {
        putchar('-');
        tc=0;
        sum(c,d);
        return;
    }
    cler(s);
    s[0]=max(c[0],d[0]);
    if(cmp(c,d)<0)
    {
        swap(c,d);
        putchar('-');
    }
    for(int i=1;i<=s[0];++i)
    {
        s[i]+=c[i]-d[i];
        if(s[i]<0)
        {
            s[i]+=mec;
            --s[i+1];
        }
    }
    while(s[s[0]]==0&&s[0]>1)
        --s[0];
}
void mul(int c[],int d[])
{
    if(tc^td)
    {
        putchar('-');
        tc=td=0;
    }
    cler(s);
    s[0]=c[0]+d[0]-1;;
    for(int i=1;i<=c[0];++i)
    {
        for(int j=1;j<=d[0];++j)
        {
            s[i+j-1]+=c[i]*d[j];
            if(i+j-1>1&&s[i+j-2]>=mec)
            {
                s[i+j-1]+=s[i+j-2]/mec;
                s[i+j-2]%=mec;
            }
        }
        if(s[i+d[0]-1]>=mec)
        {
            s[i+d[0]]=s[i+d[0]-1]/mec;
            s[i+d[0]-1]%=mec;
        }
    }
    if(s[s[0]+1]) ++s[0];
}
void div(int c[],int d[])
{
    if(tc^td)
    {
        putchar('-');
        tc=td=0;
    }
    cpy(e,d);
    int la=strlen(a)-tc,lb=strlen(b)-td;
    if(strlen(a)>strlen(b))
    {
        ly(e,strlen(a)-strlen(b));
        ly(f,strlen(a)-strlen(b));
    }
    while(cmp(c,d)>=0)
    {
        while(cmp(c,e)>=0)
        {
            dec(c,e);
            cpy(c,s);
            sum(lt,f);
            cpy(lt,s);
        }
        ry(e,1);
        ry(f,1);
    }
    if(lt[0]==0) lt[0]=1;
    write(lt);
//	write(c);
}
int main()
{
    init();
    div(c,d);
    return 0;
}
    • 1

    A/B Problem II

    信息

    ID
    970
    时间
    1000ms
    内存
    125MiB
    难度
    3
    标签
    递交数
    1
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 22ms