同余定理

2019-04-14 21:04发布

站内文章 / 模拟电子
17912 0 1241

同余定理

今天在南阳理工看了一道题，题意大致就是给你一个自然数，但是这个数的位数，注意，是位数小于等于100万，然后求10003的模，刚开始看的时候我想的是任何一个小于这个数的数求10003的模就是他本身，所以我想让两数一直相减，直到要求的数小于10003或等于10003（模即为1），但最终考虑到大数相减感觉有点麻烦，就百度关于余数的知识，最终发现了这个同余定理，记录下来，为方便自己容易查找，也为了如果大家做到这种题的时候有个较简单的解决方案。
PS:如果想要做做南阳理工的这道题可以百度关键字“南阳理工ACM_205求余数”
同余定理：(m + n) % c = (m % c + n % c) % c             (m * n) % c = ((m % c) * (m % c)) % c              m^n % c = (m % c)^n % c  从而据此写出一般性的解：#include #include #define N 9 //此程序为一般性解，在此只是以9作为范例 using namespace std; char num[1000005]; int main(void) { int m; cin >> m; while (m--) { int i; long long rem; rem = i = 0; scanf("%s",num); for (i = 0;num[i] != '

热门文章