POJ 1426 -- Find The Multiple

POJ 1426 -- Find The Multiple

大致题意：

给出一个整数n，(1 <= n <= 200)。求出任意一个它的倍数m，要求m必须只由十进制的'0'或'1'组成。

解题思路：

使用BFS，枚举由0和1组成的数，判断其是否为n的倍数

n的取值范围为：1 <= n <= 200

最高位一定是1，二叉搜索树如下所示：

我们使用数组存储每一次的枚举值（0或1）,以上是n=6的情况，

题目提到：The decimal representation of m must not contain more than 100 digits.输出的n的倍数会达到100位

随着n的增大被除数会出现大数的情况，

为解决运算过程中出现大数

可利用 同余模定理 对得到余数的方式进行一个优化

（a*b）%n = （a%n *b%n）%n

（a+b）%n = （a%n +b%n）%n

相应的搜索树可以改为：

所以，我们只要把每次进行除法运算得到的余数存储下来就行，使用数组mod进行存储

而n在200的范围内，余数值不可能超过3位数，这就解决了大数的问题

同时，要在搜索过程中进行剪枝，我们要寻找余数为0的结点，像下图中黄色的结点为余数重复出现的结点，所以，应进行剪枝。

这样进行剪枝之后，只有余数不同的才会进行处理，将最终的节点数也控制在了200（与余数的个数相同）。

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int maxn = 200+10;///余数的最大个数
 5 
 6 struct node{
 7 int num;
 8 int par;//父亲节点的下标
 9 };
10 node boolnum[maxn];//保存结果01十进制数
11 int mod[maxn];//与boolnum同步，保存每次的余数
12 bool visit[maxn];//记录余数是否已经出现过
13 int ans[maxn];
14 int n;
15 int bfs()
16 {
17     memset(visit,false,sizeof(visit));
18     int head=0,rear=1;
19     boolnum[head].num = 1;///最高位一定为1
20     boolnum[head].par = -1;///根节点的父亲记为-1
21     visit[1] = true;
22     mod[head] = 1;
23     while(head<rear)
24     {
25         int u;
26         for(int i=0;i<=1;i++)
27         {
28             u = (mod[head]*(10%n)+i)%n;
29             if(!visit[u])///当前余数没有出现过
30             {
31                 ///进行存储
32                 boolnum[rear].num = i;
33                 boolnum[rear].par = head;///存储父节点的下标
34                 mod[rear] = u;
35                 visit[u] = true;
36                 if(u==0)///得到解
37                 {
38                     int dept = rear;
39                     int temp = 0;
40                     while(dept != -1)
41                     {
42                         ans[temp++] = boolnum[dept].num;
43                         dept = boolnum[dept].par;
44                     }
45                     return temp;///返回答案的位数
46                 }
47                 rear++;
48             }
49         }
50         head++;
51     }
52 }
53 
54 int main()
55 {
56     while(cin>>n && n)
57     {
58         int temp = bfs();
59         for(int i=temp-1;i>=0;i--)
60             cout<<ans[i];
61         cout<<endl;
62     }
63     return 0;
64 }