整除的尾数

题目描述

一个整数，只知道前几位，不知道末二位，被另一个整数除尽了，那么该数的末二位该是什么呢

输入

输入数据有若干组，每组数据包含二个整数a，b（0＜a＜10000, 10＜b＜100），若遇到0 0则处理结束

输出

对应每组数据，将满足条件的所有尾数在一行内输出，格式见样本输出。同组数据的输出，其每个尾数之间空一格，行末没有空格。

样例输入

200 40 1992 95 0 0

样例输出

00 40 80
15


这个问题也是来源于HDU的，本身问题并不复杂。已知m的前几位，最后两位不知道，而这个数被n整除，可以用遍历所有可能的两位数的办法，逐个判断能否被整除，如果符合条件则输出。
我的C++实现如下：

 1 #include<iostream>
 2 #include<vector>
 3 using namespace std;
 4 int main()
 5 {
 6     vector<int> result;
 7     int m, n;
 8     for (;;)
 9     {
10         result.clear();
11         cin >> m;
12         cin >> n;
13         if (m == 0 && n == 0)
14             break;
15         for (int i = 0; i < 100; i++)
16             if ((i + m * 100) % n == 0)
17                 result.push_back(i);
18         //control output format
19         for (int i = 0; i < result.size(); i++)
20         {
21             if (result[i] < 10)
22                 cout << '0' << result[i];
23             else
24                 cout << result[i];
25             if (i == result.size() - 1)
26                 cout << endl;
27             else
28                 cout << ' ';
29         }
30     }
31     return 0;
32 }

其实这是一个整除问题，我们设要求的数为x（0 ≤ x < 100），由题意可得n | (m * 100 + x) ，所以存在整数k，使得100m + x = kn。

整理得x = kn － 100m。根据整数除法的定义，100m = n * 100m div n + 100m mod n，其中 100m div n 是整数。

因此存在整数k′ = k － 100m div n，有x = k′n － 100m mod n，根据x∈[0,100)可以解出所有可能的x的值（穷举所有可能的k′）。基于上述思路的C++实现如下：

 1 #include<iostream>
 2 #include<vector>
 3 using namespace std;
 4 int main()
 5 {
 6     vector<int> result;
 7     int m, n;
 8     int tmp;
 9     int k;
10     for (;;)
11     {
12         result.clear();
13         cin >> m;
14         cin >> n;
15         if (m == 0 && n == 0)
16             break;
17         for (k = 0;; k++)
18         {
19             tmp = k * n - ((m * 100) % n);
20             if (tmp >= 0 && tmp < 100)
21                 result.push_back(tmp);
22             if (tmp >= 100)
23                 break;
24         }
25 
26         //control output format
27         for (int i = 0; i < result.size(); i++)
28         {
29             if (result[i] < 10)
30                 cout << '0' << result[i];
31             else
32                 cout << result[i];
33             if (i == result.size() - 1)
34                 cout << endl;
35             else
36                 cout << ' ';
37         }
38     }
39     return 0;
40 }

ps.这个题的格式输出需要注意。