11.2

这两天一直纠结在同余模，
同余模两大公式：
（a*b）%n = （a%n *b%n）%n；

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

poj 1426这题，BFS+大数模，今天看到现在还是似懂非懂，先记录下来
http://blog.csdn.net/lyy289065406/article/details/6647917 这篇博客中介绍的，即可以用上一步中存储的余数代替
k10与k10+1,而记录下运算的次数对2求模就能得到答案，实在是想不到啊，mod的数组存放用到了哈夫曼树的思想，算是开了眼界，不过要运用还是...,
如果不介意用long long 的话，其实DFS可以直接解决。。。

Language:
Find The Multiple
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 35152 Accepted: 14664 Special Judge
Description

Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.
Input

The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.
Output

For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.
Sample Input

2
6
19
0
Sample Output

10
100100100100100100
111111111111111111

BFS+同余模

#include <cstdio>
#define N 6000000
int mod[N];
int ans[205];
int main(){
    int i, k, n;
    while(scanf("%d",&n),n){
        mod[1] = 1 % n;
        for(i = 2;  mod[i - 1] !=  0;  i++){
            mod[i] = (mod[i/2] * 10 + i % 2 ) % n;
        }
        i--;
        k = 0;
        while(i){
            ans[k++] = i % 2;
            i /= 2;
        }
        for(i = k - 1; i >= 0; i--){
            printf("%d",ans[i]);
        }
        puts("");
    }
    return 0;
}

DFS:

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
using namespace std;
unsigned long long answer;
int dfs(unsigned long long prenum,unsigned long long lev,int n){
    if(prenum >= lev){
        return 0;
    }
    if(lev % n == 0){
        answer = lev;
        return 1;
    }
    if(dfs(lev,lev * 10, n)){
        return 1;
    }
    return dfs(lev,lev*10+1,n);
}
int main(){
    int n;
    int i,j,k;
    while(scanf("%d",&n) != EOF){
        if(!n) break;
        if(dfs(0,1,n))
            cout<<answer<<endl;
    }
    return 0;
}

poj 2551
Ones
Time limit: 3.000 seconds
Description
Given any integer 0 ≤ n ≤ 10000 not divisibleby 2 or 5, some multiple of n is a number whichin decimal notation is a sequence of 1’s. Howmany digits are in the smallest such a multipleof n?
Input
A file of integers at one integer per line.
Output
Each output line gives the smallest integer x > 0such that p =∑x−1i=0 1×10i = a×b, where a is thecorresponding input integer, and b is an integergreater than zero.Sample Input379901Sample Output

Sample Input
3
7
9901

Sample Output
3
6
12
题意：
题意:输入一个定不能被2和整除的非负整数n,求它的最小倍数,全由一组成(十进制),即求至少需要多少个1(十进制)将其整除.
由上题的经验可知，只要每次对余数*10+1即可
AC代码：

#include <cstdio>
using namespace std;
int main(){
    int n,times,k;
    while(~scanf("%d",&n)){
        times = 1; k = 1;
        while(k % n){
        k = (k % n) * 10 + 1;
        k %= n;
        times++;
        }
        printf("%d\n",times);
    }
    return 0;
}

POJ 3279
二进制压缩枚举，还是熟悉的配方,然而还是看了答案才写出来
http://blog.csdn.net/wr132/article/details/45250529
附上代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 16;
int g[N][N],t[N][N],f[N][N];
int cnt,n,m;
int x[4] = {0,0,-1,1};
int y[4] = {-1,1,0,0};
void flip(int i,int j){
    ++cnt;
    f[i][j] = 1;
    t[i][j] = !t[i][j];
    for(int k = 0; k < 4; k++){
        if(i + x[k] > -1 && j + y[k] > -1){
            t[i + x[k]][j + y[k]] ^= 1;
        }
    }
}
bool ok(int k){
    cnt = 0;
    memcpy(t,g,sizeof(t));
    for(int j = 0; j < m; j++){
        if( k & (1<<(m-1-j)) )
            flip(0,j);
    }
    for(int i = 1; i < n; i++){
        for(int j = 0; j < m; j++){
            if(t[i-1][j])
                flip(i,j);
        }
    }
    for(int j = 0; j < m; j++){
        if(t[n-1][j])
            return false;
    }
    return true;
}
int main(){
    int ans,p;
    while(~scanf("%d%d",&n,&m)){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                scanf("%d",&g[i][j]);
            }
        }
        ans = m*m+1,p=-1;
        for(int i = 0; i < (1<<m); i++){
            if(ok(i) && cnt < ans){
                ans = cnt;
                p = i;
            }
        }
        memset(f,0,sizeof(f));
        if(p >= 0){
            ok(p);
            for(int i = 0; i < n; i++){
                for(int j = 0; j < m; j++){
                    printf("%d%c",f[i][j],j<m-1?' ':'\n');
                }
            }
        }else{
            puts("IMPOSSIBLE");
        }
    }
    return 0;
}