POJ 1426 Find The Multiple 简单dfs构造

链接: 原题网站.

题意

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

大概意思

给你一个数n，构造一个非0的由1，0组成的不超过100位数。

题解

1.用string模拟

初始值设置为1，用BFS模拟构造数列。
（很简单的字符串模板题吧！）
（不不不，这其实是一道数字题来着）

#include <algorithm>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
#define speed {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); }
const int maxn = 4e2 + 100;
const double PI = 3.14;

int a[maxn][maxn], b[maxn][maxn], dis[maxn];
int n, m, k, flag, kk;
string s;

char xmove[2] = { '0' ,'1' };//加一或者加零在最后

struct node {
	string x, y;
};

int ok(string a, int b) {
	int c = 0;
	for (int i = 0; i < a.length(); i++) {
		c = (c * 10 + a[i] - '0') % b;
	}
	if (dis[c] == 1)return 0;
	else {
		dis[c] = 1; return 1;
	}
}//判断这个数是否为出现过的数字
int slove(string a, int b) {
	int c = 0;
	for (int i = 0; i < a.length(); i++) {
		c = (c * 10 + a[i] - '0') % b;
	}
	if (c == 0)return 1;
	else return 0;
}//通过逐位运算计算是否为n的倍数

void bfs(string x)
{
	queue<node>q;
	while (!q.empty())q.pop();
	node aa, bb;
	aa.x = x;
	q.push(aa);
	while (!q.empty())
	{
		bb = q.front();
		q.pop();
		for (int i = 0; flag == 0 && i < 2; i++)
		{
			aa.x = bb.x + xmove[i];
			if (flag == 0 && !slove(aa.x, n) && ok(aa.x, n))
			{
				q.push(aa);
				if (flag == 1)break;
			}
			else if (slove(aa.x, n) && flag == 0) {
				cout << aa.x << endl;
				flag = 1;
			}
		}
		if (flag == 1)break;
	}
}

int main() {
	while (cin >> n) {
		//for (int i = 1; i <= 200;i++) {
		//	n = i;
		memset(dis, 0, sizeof dis);
		if (n == 0)break;
		s.clear();
		s = s + '1';//初始赋值为1
		flag = 0;
		bfs(s);
	}
	return 0;
}

2.数字构造

long long没爆你敢信，上面说好的不超100位的构造其实19位就够了。
（代码有点长，凑合着用吧）

#include <algorithm>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
#define speed {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); }
const int maxn = 4e2 + 100;
const double PI = 3.14;

int flag;
void bfs(int a, long long b, int k)
{
	if (k > 19)return;//long long最大19位
	if (b % a == 0&&flag==0) {
		flag = 1;
		cout << b << endl;
		return;
	}
	if(flag==0)bfs(a, b * 10, k + 1);
	if(flag==0)bfs(a, b * 10 + 1, k + 1);
}

int main()
{
	int n;
	while (cin>>n) {
		if (n == 0) break;
		flag = 0;
		bfs(n, 1, 1);
	}
	return 0;
}

本文地址：https://blog.csdn.net/zkpj12/article/details/107415502