P8782 [蓝桥杯 2022 省 B] X 进制减法题解

Rain_chr · 2023-01-02 18:07:47 · 题解

UPDATE

2023.2.21 添加了第一位读者 @Palpitate23 的问题并解答

2023.3.13 添加了第二位读者 @abc1352758620 的问题并解答

2023.4.4 修了公式中不完善的地方。

question & answer

Q : 为什么计算 ka 和 kb 时也要对 10^7 取模啊，题目的意思不是最后相减完再取模就可以了吗？

A : 是这样的，因为两个数 A 和 B 是 10^5 级别的，如果先算出值再减法，没有任何一种变量存的下。而且越到后面这一位的权值越大，呈指数级别上涨，除非使用高精度，否则没有办法计算。而且取模运算有一个特性，加法和乘法可以任意取模，所以我就每计算一遍都取模。

问题来自：@Palpitate23

Q ：如果某一位的数字，出现 a_i<b_i ，那么 a_i-b_i 就变成负数了，是否需要借位？如果为负数，能否得出答案？

A ：思考的很全面，因为题面中提到了 A−B 的结果的最小可能值转换为十进制后再模 10^7 的结果，所以答案一定是一个取模意义下的数值。

借位其实就是直接取模后减法，即使答案是一个负数，但是在取模意义下的结果，所以我们直接进行取模意义下的减法即可。

另外，其实题目中保证了 A-B 非负。

问题来自：@abc1352758620

在此由衷感谢！

题意简述

这题其实非常好理解，只是有一点点要注意。

平常的 n 进制中，第 i 位代表的值是 a_i \times n^i ，其中 i 从0开始计数，从右往左数。

但在此题中，由于进制不同，无法以上方式子得到权值，第i位的权值是 a_i \times \prod_{j=0}^i n_i ，其中 n_i 是第i位的权值，这点值得谨记。

题目分析

对于每一位， a_i 和 b_i ,显然这一位的进制 x 必须满足 x>\max(a_i,b_i) ,不然的话没法儿表示。又因为要使得差尽可能小，所以每一位进制就是 \max(a_i,b_i)+1 ，这里是贪心思想。

最后直接上代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100010];
int b[100010];
int c[100010]; 
int d[100010];
const int mod=1e9+7;
signed main()
{
    int n; //输入部分 
    cin>>n;
    int ma;
    cin>>ma;
    for(int i=ma;i;i--)
        cin>>a[i];
    int mb;
    cin>>mb;
    for(int i=mb;i;i--)
        cin>>b[i];

    for(int i=max(ma,mb);i;i--) //处理进制 
        c[i]=max(a[i],b[i])+1;
    for(int i=max(ma,mb);i;i--) //最低进制是二进制 
        c[i]=c[i]>2?c[i]:2;

    d[1]=1; //处理每一位的价值 
    for(int i=2;i<=max(ma,mb);i++)
        d[i]=(d[i-1]*c[i-1])%mod;

    long long ka=0,kb=0; //统计价值 
    for(int i=ma;i;i--)
        ka+=a[i]*d[i],ka%=mod;
    for(int i=mb;i;i--)
        kb+=b[i]*d[i],kb%=mod;

    cout<<(ka-kb+mod)%mod; //特别注意：模意义下的减法 
    return 0;
}

思考提升

如果题目要求每一位的进制互不相同呢？

提示：考虑求每一位权值的式子。

结论：还是贪心，让低位的进制尽可能的小，以此保证后面的权值尽可能的小。

P8782 [蓝桥杯 2022 省 B] X 进制减法 题解