Zhao70's Blog

POJ1426 Find The Multiple

发表于 | 分类于

题目大意

给定一个数字 n, 求 n 的一个倍数 m. m 的要求是一个只由 0 和 1 构成的十进制数字.

题目思路

对于一个 m 第一位肯定为 1, 剩下的每一位有 0 和 1 两种情况, 如果进行穷举, 数会变得很大. 因此, 需要运用同余模定理, 减少中间数字规模.

知识点

1
2
（a*b）%n = （a%n *b%n）%n
（a+b）%n = （a%n +b%n）%n

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <cstring>
using namespace std;
const int maxV = 999999;
int m[maxV];
int rec[maxV];
int main() {
	int val;
	while (cin >> val && val) {
		memset(m, 0, sizeof(m));
		m[1] = 1;
		int i;
		for (i = 2; m[i - 1] != 0; i++) {
			m[i] = (m[i / 2] * 10 + i % 2) % val;
		}
		int len = 0;
		i--;
		while (i) {
			rec[len++] = i % 2;
			i /= 2;
		}
        while(len)
            cout << rec[--len];
		cout << endl;
	}
	return 0;
}

参考链接

POJ1426-Find The Multiple
poj 1426 Find The Multiple搜索BFS的思想+ 同余模定理+二叉树+01哈夫曼编码