首页 > 代码库 > 解题报告1010 诡秘的余数

解题报告1010 诡秘的余数

Time Limit:1000MS  Memory Limit:32768K

Description:

不可否认,fans是一名数学天才,大家都这么说。天才fans的两大最新发现如下:(1) 正整数n除3的余数,等价于正整数n的各位数字之和除3的余数;(2) 正整数n除9的余数可以通过这样的方法来计算:计算n 的各位数之和,设为m,如果m已经是一位数,那么余数就是m;否则设n=m,重新计算n的各位数之和m,直到m成为一个一位数。然而,正整数除1,2,4,5,6,7,8,也存在类似的性质吗?这真是一个难题啊!fans想睡觉了,不去管了。现在请你计算一下正整数n除一位数m的余数。文件中有一些数对,一为大整数(可能大到100位)n,另一为一位数m(m>0)。求其n除以m的余数。

Sample Input:

23 7123 9

Sample Output:

26


在百度知道上看到的算法,不知道原理。
123 % 9 = 6
1 % 9 =1
(1*10 + 2) % 9 = 3
(3*10 + 3) % 9 = 6
规律:从第一位开始,将前面的余数*10与当前位相加,再模余数。

代码如下:
 1 #include<iostream> 2 #include<string> 3 #include<strstream> 4 using namespace std; 5 int main() 6 { 7     string n; 8     int m; 9     while(cin>>n>>m)10     {11         int pre=0;12         for(int i=0;i<n.length();i++)13         {14             int t=(int)(n[i]-0);15             if(i==0) pre=t%m;16             else17                 pre=(pre*10+t)%m;    18         }19         cout<<pre<<endl;20     }21     return 0;22 }

 

解题报告1010 诡秘的余数