POJ 1465-Multiple（BFS-最小整倍数）

蔚落 2022-09-24 10:30 60阅读 0赞

# Multiple #

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 32768K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 7106</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 1524</td> 
  </tr> 
 </tbody> 
</table>

Description

a program that, given a natural number N between 0 and 4999 (inclusively), and M distinct decimal digits X1,X2..XM (at least one), finds the smallest strictly positive multiple of N that has no other digits besides X1,X2..XM (if such a multiple exists).

Input

The input has several data sets separated by an empty line, each data set having the following format:  
  
On the first line - the number N  
On the second line - the number M  
On the following M lines - the digits X1,X2..XM.

Output

For each data set, the program should write to standard output on a single line the multiple, if such a multiple exists, and 0 otherwise.  
  
An example of input and output:

Sample Input

22
    3
    7
    0
    1
    
    2
    1
    1

Sample Output

110
    0

Source

[Southeastern Europe 2000][]

## 题目意思： ##

给定一个自然数N，以及M个不同的数字X 1，X 2，...X m。求N的最小正整数倍数，使得满足这个数的每个数字都是M个数字中的其中一个。

## 解题思路： ##

BFS广搜。

思路：利用给定的M个数，组成不同的数，比如7 0 1，可以依0 1 7的序组成0 1 7 10 11 17 77 100 110 111 117……等等等等，然后对这些数进行判断是否整除N。

注意 剪枝：

对于给定两个数A，B，如果A和B模N都相同，设为C，即：

A=x\*N+C

B=y\*N+C

那么如果在A后面加上一个数字能够被N整除，则在B后面加上这个数字也肯定可以被N整除

即：(A\*10+X)%N==(B\*10+X)%N

因此可以利用模N的结果进行判重，只保留相同余数的最小数。

注意 特判“0”的情况。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=5050;
    int n,m;
    int digit[10];//给定的M个数字
    bool flag[maxn];//剪枝用，标记当前余数是否出现
    
    struct Node
    {
        int digit;//当前状态的各位值
        int r;//当前状态值%N的余数
        int pre;//当前状态的各位值的连接指针,用来找到所有当前状态的位
    } Q[maxn];
    
    int BFS()
    {
        memset(flag,0,sizeof(flag));
        int front=0,tail=1;
        Q[front].digit=0;
        Q[front].r=0;
        Q[front].pre=-1;
        while(front<tail)
        {
            Node node=Q[front];//当前节点
            int r=node.r;//之前算出的老余数
            for(int i=0; i<m; i++)
            {
                int nr=(r*10+digit[i])%n;//本次产生的新余数
                if(!flag[nr] && (node.pre!=-1 || digit[i]!=0))//错误,忘写了后面这段,我们要保证后继不能生成0
                {
                    flag[nr]=true;//剪枝用，标记当前余数出现
                    node.r=nr;
                    node.digit=digit[i];
                    node.pre=front;
                    Q[tail++]=node;//存入结构体队列中
                    if(nr==0) return tail-1;//余数为0表示能整除
                }
            }
            ++front;//队列递增加1
        }
        return -1;
    }
    void print(int ans)
    {
        if(ans>0)
        {
            print(Q[ans].pre);
            cout<<Q[ans].digit;
        }
    }
    int main()
    {
    
        while(cin>>n)
        {
            cin>>m;
            for(int i=0; i<m; i++)
                cin>>digit[i];
            sort(digit,digit+m);//输入的数列递增排序
            if(n==0)//特判0
            {
                puts("0");
                continue;
            }
            int ans=BFS();//广搜
            if(ans==-1) puts("0");//不存在
            else
            {
                print(ans);
                puts("");//输出格式
            }
        }
        return 0;
    }
    /**
    22
    3
    7
    0
    1
    
    2
    1
    1
    **/

[Southeastern Europe 2000]: http://poj.org/searchproblem?field=source&key=Southeastern+Europe+2000