学步园

这道题我想吐槽的是，卧槽为什么我的第一种方法竟然可以AC，这也太不严谨了。

题目概述：

这道题是说给定一个1-200之间的数n，在他的倍数中找到一个数，这个数的要求是所有位数只为0或者1，输出这个数。

算法思想：

开始想的是枚举每个倍数，然后每个倍数去检测是不是0还是1，觉得卧槽肯定越界，肯定越界，肯定越界，然后就又想了一下没想出来就去看解题报告了。

嗯然后看到第一种方法，是用BFS枚举0和1，然后每次得到数字之后都mod一下n看能不能整除。

坑的地方就在于在long long范围内，这个方法竟然能够实现，也就是说所有结果的倍数没有一个超过18位的，这跟题目描述的几百位不同呀少年。

好了这个方法很好理解。我把代码放在这里，然后值得看的应该是下面的一个代码。

代码部分：

#include <iostream>
#include <queue>
using namespace std;
int n;
void bfs() {
	queue<long long> q;
	q.push(1);
	long long x = 1, pos;
	while (!q.empty()) {
		pos = q.front();
		q.pop();
		x = pos * 10;
		if (x % n == 0) {
			cout << x << endl;
			break;
		}
		q.push(x);
		x++;
		if (x % n == 0){
			cout << x << endl;
			break;
		}
		q.push(x);
	}
}


int main() {
	while (cin >> n && n != 0) {
		if (n == 1) {
			cout << n << endl;
			continue;
		}
		bfs();
	}
	return 0;
}

真正值得看的代码：

这个用到了同余模定理，简单的来说就是mod这个符号可以“乱加”。是厉害。

http://user.qzone.qq.com/289065406/blog/1303946967

//Memory Time
//2236K  32MS 

#include<iostream>
using namespace std;

int mod[524286];  //保存每次mod n的余数
                  //由于198的余数序列是最长的
                  //经过反复二分验证，436905是能存储198余数序列的最少空间
                  //但POJ肯定又越界测试了...524286是AC的最低下限，不然铁定RE

int main(int i)
{
	int n;
	while(cin>>n)
	{
		if(!n)
			break;

		mod[1]=1%n;  //初始化，n倍数的最高位必是1

		for(i=2;mod[i-1]!=0;i++)  //利用同余模定理，从前一步的余数mod[i/2]得到下一步的余数mod[i]
			mod[i]=(mod[i/2]*10+i%2)%n;
		             //mod[i/2]*10+i%2模拟了BFS的双入口搜索
		             //当i为偶数时，+0，即取当前位数字为0  。为奇数时，则+1,即取当前位数字为1

		i--;
		int pm=0;
		while(i)
		{
			mod[pm++]=i%2;   //把*10操作转化为%2操作，逆向求倍数的每一位数字
			i/=2;
		}
		while(pm)
			cout<<mod[--pm];  //倒序输出
		cout<<endl;
	}
	return 0;
}