这题数据是不是有点弱
查看原帖
这题数据是不是有点弱
507348
__vector__楼主2024/3/11 19:56

这个代码(在版本 II 也) AC 了,但是我随机造了个数据,就本地寄了。

如果数据错了请提醒一下,谢谢。
input:

1
2  

正常应该是 0,但是我的程序没有输出。

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back()
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int T;
const int maxlen=40005;
struct Big_Integer{
    int bit[maxlen];
    int len=0;
    Big_Integer(int _init=0){
        while(_init){
            ++len;
            bit[len]=_init%10;
            _init/=10;
        }
    }
    Big_Integer(char* s){
        len=strlen(s+1);
        for(int i=1;i<=len;i++){
            bit[i]=s[len-i+1]-'0';
        }
    }
    Big_Integer operator*(const int b)const{
        Big_Integer res;
        res.len=len;
        FOR(i,1,len){
            res.bit[i]=bit[i]*b;
        }
        FOR(i,1,len-1){
            res.bit[i+1]+=res.bit[i]/10;
            res.bit[i]%=10;
        }
        while(res.bit[len]>=10){
            res.bit[len+1]=res.bit[len]/10;
            res.bit[len]%=10;
            res.len++;
        }
        return res;
    }
    Big_Integer operator/(const Big_Integer& b)const{
        Big_Integer vis;
        Big_Integer self;
        self.len=len;
        FOR(i,1,len)self.bit[i]=bit[i];
        FOR(i,len+1,len+b.len-1)self.bit[i]=0;
        Big_Integer temp;// 暂时保存乘法结果
        Big_Integer res;
        if(len<b.len)return res;
        for(int i=len-b.len+1;i>=1;i--){
            // 从高位到低位枚举答案
            // 目前是 i 位
            for(int num=9;num>=0;num--){
                // 枚举答案 i 位的值 num
                FOR(j,1,b.len){
                    // 枚举 b 第 j 位 
                    temp.bit[i+j-1]=b.bit[j]*num;
                }
                FOR(pos,i,i+b.len-2){
                    temp.bit[pos+1]+=temp.bit[pos]/10;
                    temp.bit[pos]%=10;
                }
                int pos=i+b.len-1;
                while(temp.bit[pos]>=10){
                    temp.bit[pos+1]=temp.bit[pos]/10;
                    temp.bit[pos]%=10;
                    pos++;
                }
                // pos 是 temp 最高位
                // temp 存储了 i 位与 b 的乘法结果,然后 self 将试着减去它
                vis.bit[pos+1]=self.bit[pos+1];
                FOR(j,i,pos)vis.bit[j]=self.bit[j];
                FOR(j,i,pos){
                    if(temp.bit[j]<=self.bit[j]){
                        self.bit[j]-=temp.bit[j];
                    }else{
                        self.bit[j]+=10;
                        self.bit[j]-=temp.bit[j];
                        self.bit[j+1]-=1;// 不足,借位
                    }
                }
                if(self.bit[pos+1]<0){
                    // 不可以
                    FOR(j,i,pos){
                        self.bit[j]=vis.bit[j];// 还原
                    }
                    self.bit[pos+1]=vis.bit[pos+1];
                }else{
                    res.bit[i]=num;
                    break;
                }
            }
        }
        res.len=len-b.len+1;
        while(!res.bit[res.len])res.len--;
        return res;
    }
};
char n[10000*4],m[40000];
int main()
{
    scanf("%s",n+1);
    scanf("%s",m+1);
    Big_Integer _n(n),_m(m);
    auto res=_n/_m;
    REP(i,res.len,1){
        printf("%d",res.bit[i]);
    }    
    if(res.len==0)puts("0");
	return 0;
}  
2024/3/11 19:56
加载中...