P4282 题解

· · 题解

作为一道模板题，某蒟蒻认为难度系数不大。

题目描述:

主要思想：

看到 N≤10^5，我们意识到这道题要用到高精！！！
在计算出结果后，我们需要对一个数 M+1 取模，而高精度取模是很麻烦的 ( 其实是我不愿意写 ) 所以我找到了一个可以巧妙避免取模的方法那就是:
直接输出 N 位的值。

一个小坑点: 输入的数应该需要 reverse 一下。

至于如何不取模，以下给出证明。
已知 M 为 N 位可变进制数中的最大整数。
当运算符为加时: 如果两个运算数的和大于了 M,那么 最后的值只会影响到 N+1 位，而1…N 位不会被影响，所以输出 N 位就好。
当运算符为减时: 如果两个运算数的差小于0,根据取模的性质:一个负数模一个正数答案也会是正数,所以答案也只输出 N 位就好。

#include <bits/stdc++.h>
#define in scanf
#define out printf
using namespace std;
int x[100005];
int a[100005];
int b[100005];
int c[100005];
int number,mod,sum;
char op;
int main(){
    in("%d",&number);
    //原来都是正着输入的,可是因为我懒,都改成倒着输入了
    for(int rp=number;rp>=1;rp--){
        in("%d",&x[rp]);
    }
    for(int rp=number;rp>=1;rp--){
        in("%d",&a[rp]);
    }
    cin>>op; //此处是一个坑点：假如你用scanf就会多读一个空格 
    for(int rp=number;rp>=1;rp--){
        in("%d",&b[rp]);
    }
//  到此为止都是输入 
    if(op=='+'){
//      当运算符是+时，执行加法操作 
        for(int rp=1;rp<=number;rp++){
            c[rp]=(a[rp]+b[rp]+sum)%x[rp];
            sum=(a[rp]+b[rp]+sum)/x[rp];
            /*
            十进制高精：
                c[rp]=(a[rp]+b[rp]+sum)%10;
                sum=(a[rp]+b[rp]+sum)/10;
                相比之下，就是把进制改成了x[rp]进制 
            */ 
        }
    }else{
        for(int rp=1;rp<=number;rp++){//减法操作
            if(a[rp]<b[rp]){
                a[rp]+=x[rp];
                a[rp+1]--;
            }
            a[rp]-=b[rp];
            c[rp]=a[rp];
//          同样把十进制改为了x[rp]进制 
        }
    }
    for(int rp=number;rp>=1;rp--){-
        out("%d ",c[rp]); //  输出答案c数组 
    }

    return 0;
}

蒟蒻的第一篇题解，管理员大大求过qwq