大整数取模-思路及实现
大整数取模--思路及实现
1.取模的常用公式：
一 . (a+b)mod n = ((a mod n)+(b mod n) mod n
二 . (a-b)mod n = ((a mod n)-(b mod n)+n) mod n
三 . ab mod n = (a mod n)(b mod n) mod n
比如，求两个整数的乘积的模，因为乘积可能超过INT_MAX, 故应该用long long存储中间值。
int mul_mod(int a, int b, int n) { a %= n; b %= n; return (int) ((long long)a*b % n); }
2.应用：大整数取模
思路：首先，将大整数分解成这种形式：1234 = ((1*10+2)*10+3)*10+4
不难发现，这种形式可以应用我们前面的取模公式，分步取模。
#include <cstdio> #include <cstring> char a[10000 + 10]; int main() { int b, len; while(~scanf("%s%d", a, &b)){ len = strlen(a); int ans = 0; for(int i = 0; i < len; i++) ans = (int)(((long long) ans*10 + a[i] - '0') % b); //long long保存中间结果 printf("%d\n", ans); } return 0; }