#include <bits/stdc++.h> using namespace std; int change(string& str){ int tmp = str[str.size()-1] - '0'; str.erase(str.size()-1, 1); return tmp; } bool zero(string str){ for(auto s : str) if(s != '0') return false; return true; } int main() { long long n, tmp, plus; string N, A, B, result; cin >> N >> A >> B; if(zero(A) && zero(B)) {cout << 0; return 0;} // 擦除高位不必要的0 while(A[0] == '0') A.erase(0, 1); while(B[0] == '0') B.erase(0, 1); // 最低位没有上一位的进位额外处理一次 // 获取十进制时候的和 tmp = change(A) + change(B); // 转换为当前位进制 n = change(N); // 特殊判断 0 十进制 if (n == 0) n = 10; // 加到结果上 result.insert(0, 1, tmp % n + '0'); // 取得进位数 plus = tmp / n; while(A.size() && B.size()){ // 获取十进制时候的和 tmp = change(A) + change(B)+ plus; // 转换为当前位进制 n = change(N); // 特殊判断 0 十进制 if (n == 0) n = 10; // 加到结果上 result.insert(0, 1, tmp % n + '0'); // 取得进位数 plus = tmp / n; } while(A.size()){ // 获取十进制时候的和 tmp = change(A) + plus; // 转换为当前位进制 n = change(N); // 特殊判断 0 十进制 if (n == 0) n = 10; // 加到结果上 result.insert(0, 1, tmp % n + '0'); // 取得进位数 plus = tmp / n; } while(B.size()){ // 获取十进制时候的和 tmp = change(B) + plus; // 转换为当前位进制 n = change(N); // 特殊判断 0 十进制 if (n == 0) n = 10; // 加到结果上 result.insert(0, 1, tmp % n + '0'); // 取得进位数 plus = tmp / n; } // 加上最高的进位 if(plus != 0) result.insert(0, 1, plus + '0'); cout << result; return 0; }
#include <bits/stdc++.h> using namespace std; int main() { // 最低位时进位为0 int mod, tmp, carry = 0, output = false; string N, A, B, ans; cin >> N >> A >> B; string tmpA(N.size() - A.size(), '0'); A = tmpA + A; string tmpB(N.size() - B.size(), '0'); B = tmpB + B; for(int i = N.size() - 1; i >= 0; i--) { // 转换为当前位进制 mod = (N[i] == '0') ? 10 : N[i] - '0'; // 插入到结果上 ans.insert(0, 1, (A[i] + B[i] - '0' * 2 + carry) % mod + '0'); // 取得进位数 carry = (A[i] + B[i] - '0' * 2 + carry) / mod; } // 加上最高的进位 if(carry != 0) ans.insert(0, 1, carry + '0'); for(auto a: ans) if(a != '0' || output == true){ cout << a; output = true; } if(output == false) cout << 0; }
刚开始只过了样例得了 10 分,当时想 int 应该有 2^10 左右,那么乘以平方的 long long 应该也有 2^20 才对。结果看了别人的文章发现 int 只有 10^9 而 long long 只有 10^18 unsigned long long 不过 10^19 还是没有达到题目要求的 20 位数字。所以只能改成 string。
改了之后用粗暴的复制粘贴改改变量就AC了,虽然看起来有点不美观,重复了三个近似的循环代码。
int, long等数据类型取值范围与10的数量级对照
还有要注意一些测试点,比如老生常谈的 0 ,这里不仅仅只是一个 0 还可能是多个 0000 类型。并且由于有进位,最后的时候进位存在时需要加在最高位。以及输入的高位数字存在 0 的情况。
测试点1 3
最开始判断是否全部为 0 是想用 stoi() 转换成整形的,但是输入数据发现会抛出异常。查了查这个函数,发现它只能够转换 int 范围的整形,所以这里的 20 位数字也超过这个函数的范围了。
故当时手写了一个函数判断是否全为 0 。
看了看别人怎么写。发现了很多神奇的写法。
一个是这个 string 字符串的初始化,虽然以前见过这次记一记。变量名的括号后面的参数分别是长度以及初始化用的字符。
string初始化及赋值方式
一个是化简了三个循环代码,通过高位补零的方式来通过统一的下标操控同样的数字位。
而这个需要配合另外的方法使用,在后面会定义给一个输出的变量 output 如果结果不为 0 的时候就会输出一次,那么就会赋值 true 让后面即便有 0 的时候也继续输出。
这种方式有点像通过这个变量,将高位 0 的情况与右边要输出的情况划了一个分界线,当一个非 0 的时候就将右边划为输出列了,即便右边可能仍然存在 0 。
还有进位可以最开始的时候定义为 0 ,这样加减的时候就不需要提出来,直接放在循环里面。
还有就是,由于数字是左到右为高位到低位,但是字符串的低位时从右边开始,所以如果要按照数字的低位到高位,就得将下标反过来,从 size - 1 开始。
参考代码