NYOJ 205

大数取模算法：

这个又不同于幂取模算法，对于几百万位的数字取模，直接的方法是行不通的。最好利用数论的知识 (a*b)%c = ((a%c)*b)%c ;
利用这个公式我们只要从n的一次方开始不断计算，乘于一个数同时就对其求余，这样就可以在不溢出的情况下得出最后的结果。

设bignum的个位数是x 
设 m = (bignum-x)/10 ;
 解得 bignum = 10*m + x ;
所以： bignum%n = (10*m+x)%n = (10*m)%n + x%n = ((m%n)*10)%n + x%n
                    有了这个等式就可以计算出最后的结果了。我们可以用递归或者循环来实现。

原题：

求余数

时间限制：1000 ms  |  内存限制：65535 KB

难度：3

描述

现在给你一个自然数n，它的位数小于等于一百万，现在你要做的就是求出这个数除10003之后的余数

输入

第一行有一个整数m(1<=m<=8),表示有m组测试数据；
随后m行每行有一个自然数n。

输出

输出n整除10003之后的余数，每次输出占一行。

样例输入

3

4

5

465456541

样例输出

4

5

6948

AC代码：

 #include<cstdio>

 #include<iostream>

 using namespace std;

 int main(){

     int N;

     scanf("%d",&N);

     while(N--){

         string M;

         cin >> M;

         int num = ;

         int i;

         for(i = ; i < M.size();i++){

             num = (num* + (M[i] - ''))%;

         }

         cout << num << endl;

     }

     return ;

 }