同余定理（求余数）

Bertha 。 2022-07-15 11:29 214阅读 0赞

现在给你一个自然数n，它的位数小于等于一百万，现在你要做的就是求出这个数除10003之后的余数  
  
  
输入  
第一行有一个整数m(1<=m<=8),表示有m组测试数据；  
随后m行每行有一个自然数n。  
  
  
输出  
输出n整除10003之后的余数，每次输出占一行。  
  
  
样例输入  
3  
4  
5  
465456541  
  
  
样例输出  
4  
5

6948

代码如下：

**\[cpp\]**  [view plain][]  [copy][view plain]

1.  /\* 
2.  同余定理：(a+b)%c=((a%c)+(b%c))%c 
3.  m%n举例： 
4.  123 % n = ((1%n\*10%n+2%n)%n\*10%n+3%n)%n 
5.  (m+n)%c=(m%c+n%c)%c;  
      
       (19+4)%3=(19%3+4%3)%3;  
      
    (m\*n)%c=((m%c)\*(n%c))%c;  
      
    m^n%c=(m%c)^n%c;  
      
       3^11%8=(3^10 \* 3^1)%8=((3^2)^5 \* 3^1)%8=((8+1)^5 \* 3^1)%8
    
      
    
6.  \*/  
7.  \#include<iostream>  
8.  \#include<string>  
9.  \#include<string.h>  
10. \#include<cstdio>  
11. \#include<algorithm>  
12. **using** **namespace** std;  
13.   
14. **int** main()  
15. \{  
16.     //freopen("Input.txt", "r", stdin);  
17.     **int** N, i, num, len;  
18.     scanf("%d", &N);  
19.     **while**(N--)  
20.     \{  
21.         num = 0; 
22.         **char** str\[1000010\];          
23.         scanf("%s", str);
24.         len = strlen(str);
25.         **for**(i = 0; i != len; ++i)
26.         \{ 
27.             num = (num \* 10 + (**int**)(str\[i\] - '0')) % 10003;
28.         \} 
29.         printf("%d\\n", num);  
30. 
31.     \}  
32.     **return** 0;  
33. \}

[view plain]: http://blog.csdn.net/niushuai666/article/details/6606535#

发表评论取消回复

表情：

评论列表（有 0 条评论，214人围观）

还没有评论，来说两句吧...

相关阅读

相关同余模定理

同余模定理定义： • 所谓的同余，顾名思义，就是许多的数被一个数d去除，有相同的余数。d数学上的称谓为模。如a=6,b=1,d=5,则我们说a和b是模d同余的。因为他

谁借莪１个温暖的怀抱￠/ 2022年08月21日 00:19/ 0 赞/ 189 阅读

相关 LightOJ 1214 - Large Division【同余定理】

1214 - Large Division <table> <tbody> <tr> <td title="normal judge" style="col

我会带着你远行/ 2022年08月18日 02:35/ 0 赞/ 170 阅读

相关中国余数定理

我国古代数学名著《孙子算经》载有一道数学问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”这里的几何指多少的意思。翻译成数学语言就是：求正整数N，使

「爱情、让人受尽委屈。」/ 2022年08月13日 13:43/ 0 赞/ 264 阅读

相关 pku 2115 C Looooops 同余定理

\include <stdio.h> long long mod(long long a,long long b) \{ return (a % b + b) % b; \}

- 日理万妓/ 2022年08月04日 15:53/ 0 赞/ 159 阅读

相关【light oj1078】Integer Divisibility（同余定理）

<table style="margin:0px; padding:0px"> <tbody style="margin:0px; padding:0px"> <tr

刺骨的言语ヽ痛彻心扉/ 2022年07月16日 02:41/ 0 赞/ 165 阅读

相关同余定理（求余数）

现在给你一个自然数n，它的位数小于等于一百万，现在你要做的就是求出这个数除10003之后的余数输入第一行有一个整数m(1<=m<=8),表示有m组测试数

左手的ㄟ右手/ 2022年07月15日 11:29/ 0 赞/ 200 阅读

相关同余定理（求余数）

现在给你一个自然数n，它的位数小于等于一百万，现在你要做的就是求出这个数除10003之后的余数输入第一行有一个整数m(1<=m<=8),表示有m组测试数

Bertha 。/ 2022年07月15日 11:29/ 0 赞/ 215 阅读

相关同余定理

同余运算及其基本性质 100除以7的余数是2，意思就是说把100个东西七个七个分成一组的话最后还剩2个。余数有一个严格的定义：假如被除数是a，除数是b（假设它们均为正整数

悠悠/ 2022年06月17日 08:29/ 0 赞/ 228 阅读

相关【转载】--同余定理

同余运算及其基本性质 100除以7的余数是2，意思就是说把100个东西七个七个分成一组的话最后还剩2个。余数有一个严格的定义：假如被除数是a，除数是b（假设它们均

矫情吗；*/ 2022年06月10日 12:28/ 0 赞/ 952 阅读

相关【算法】同余定理及快速幂求模

文章目录定义及其性质大数的高精度对单精度取模快速幂取模(次方求模) 定义及其

港控/mmm°/ 2022年04月01日 10:00/ 0 赞/ 369 阅读