POJ1426-Find The Multiple（BFS+同余）

题目链接
题意：找出一个n的倍数，这个数只含1和0。

参考博客

题记：可以用BFS的思想去做，每位数只有1和0两种情况（第一位必须是1）。那么我们BFS时是类似于一个二叉树的形状（最好画图理解）

同余定理：
（a*b）%n = （a%n *b%n）%n
（a+b）%n = （a%n +b%n）%n

具体证明可以看上面的参考博客。

下图可做参考（字有些难看 ）。
图中n取6，黑体字为当前数字，红体字为当前数字余6的余数，蓝体字是当前数字的序号（BFS的顺序）。可以看出是和二叉树是一样的，所以可以用二叉树的性质去做。每个节点（除了父节点）都是由父节点10或10+1得到的，[i/2]10和[i/2]10+1。序号是偶数是10，序号是奇数是10+1。

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e6;
int mod[N];//mod数组存余数
int main(){
    int n;
    while(cin>>n){
        if(!n) break;
        mod[1]=1%n;//最高位必定是1
        int i;
        //cout<<mod[1]<<' ';
        for(i=2;mod[i-1]!=0;i++){
            mod[i]=(mod[i/2]*10+i%2)%n;
            //类似于线段树的建树过程的BFS
            //cout<<mod[i]<<' ';
        }
        //cout<<endl;
        i--;
        //cout<<i<<endl;
        int temp=0;
        while(i){
            mod[temp++]=i%2;
            //在二叉树编号为偶数的填0
            //奇数的填1
            i/=2;
        }
        while(temp)
            cout<<mod[--temp];
        cout<<endl;
    }
    return 0;
}