【大数取模】HDOJ-1134、CODEUP-1086

1086: 大数取模

题目描述

现给你两个正整数A和B，请你计算A mod B。
为了使问题简单，保证B小于100000。

输入

输入包含多组测试数据。每行输入包含两个正整数A和B。A的长度不超过1000，并且0<B<100000。

输出

对于每一个测试样例，输出A mod B。

样例输入

2 3 12 7 152455856554521 3250

样例输出

2 5 1521

【概念】

　　(a+b)%n =(a%n+b%n)%n

　　(a-b)%n = (a%n-b%n)%n

　　实话说刚开始我没看懂。

　　代码：

 1 int mod(char str[],int num)
 2 {
 3     int number[MAXN],i,d = 0;
 4     int len = strlen(str);
 5     //将字符串数组转化为数字数组
 6     for(i = 0;i < len;i++)
 7         number[i]=str[i]-'0';
 8     int remainder=0;
 9     for(i = 0;i < len;i++)
10     {
11         remainder=(remainder * 10 + number[i]) % num;
12     }
13     return remainder;
14 }

　　举个例子：

　　　　123 % 4 = 3

　　　　-1- (0 * 10 + 1) % 4 = 1; -2- (1 * 10 + 2) % 4 = 0;

　　　　-3- (0 * 10 + 3) % 4 = 3; -4- 得到最终结果3

　　　　也就是模拟了除法竖式的过程

【练习题】

题目链接：http://arena.acmclub.com/problem.php?id=1086

　　　　代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 const int MAXN = 1000;
 4 int mod(char str[],int num)
 5 {
 6     int number[MAXN],i,d = 0;
 7     int len = strlen(str);
 8     //将字符串数组转化为数字数组
 9     for(i = 0;i < len;i++)
10         number[i]=str[i]-'0';
11     int remainder=0;
12     for(i = 0;i < len;i++)
13     {
14         remainder=(remainder * 10 + number[i]) % num;
15     }
16     return remainder;
17 }
18 int main(){
19     char A[MAXN];
20     int B;
21     //'~'取反符号，当输入值不符合要求时停止
22     //while(~scanf("%s %d",A,&B)){
23 
24     //判断有无结尾符结束
25     //while(scanf("%s %d",A,&B) != EOF){
26 
27     //如果两个参数均被读入则返回参数个数
28     while(scanf("%s %d",A,&B) == 2){
29         printf("%d
",mod(A,B));    
30     }    
31     return 0;
32 }

下面这种方法是运用到了C++ 的大数类，大数模板

　　　　C++ 大数模板链接：http://www.cnblogs.com/zhengbin/p/4368182.html

　　　　代码：

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int MAXN = 9999;
 5 const int DLEN = 4;
 6 char str[1010];
 7 int modd;
 8 class BigNum{
 9     private:
10         int a[1010];
11         int len;
12     public:
13         BigNum(){len = 1;memset(a,0,sizeof(a));}
14         BigNum(const char*);
15         int operator %(const int &)const;
16 };
17 BigNum::BigNum(const char*s)     //将一个字符串类型的变量转化为大数
18 {
19     int t,k,index,l,i;
20     memset(a,0,sizeof(a));
21     l=strlen(s);   
22     len=l/DLEN;
23     if(l%DLEN)
24         len++;
25     index=0;
26     for(i=l-1;i>=0;i-=DLEN)
27     {
28         t=0;
29         k=i-DLEN+1;
30         if(k<0)
31             k=0;
32         for(int j=k;j<=i;j++)
33             t=t*10+s[j]-'0';
34         a[index++]=t;
35     }
36 }
37 int BigNum::operator %(const int & b) const{    //大数对一个int类型的变量进行取模运算    
38     int i,d=0;
39     for (i = len-1; i>=0; i--)
40     {
41         d = ((d * (MAXN+1))% b + a[i])% b;  
42     }
43     return d;
44 }
45 int main(){
46     while(~scanf("%s %d",str,&modd)){
47         BigNum big(str);
48         cout << big % modd << endl;
49     }
50     return 0;
51 }