东华大学oj n的倍数

N的倍数

时间限制: 2s

类别: 函数->中等

问题描述

明明的爸爸在研究一个复杂的数学问题，研究了很长时间都没有结果。明明看见后就问爸爸在研究什么。明明的爸爸回答说：“我在研究一个整数的倍数问题，想找到某个数的倍数……”明明还没有等他爸爸说完，就抢着说：“这不是很简单嘛，你把这个整数乘以1，乘以2，……，就能得到很多的倍数呀。”明明的爸爸当然知道这种方法，但是他接着说：“这样的方法找倍数当然容易，但是我找的倍数有一个特点，那个倍数只能由0或1组成，且应该尽量的小。例如一个自然数2，它符合要求的那个倍数就是10。”这下明明明白为什么爸爸研究了那么多时间都还没有研究出结果了，因为随着数字的增大，找到它的符合要求的倍数越来越难。明明想帮他爸爸解决这个问题，于是他来求助于你，能否帮他爸爸写一个程序，来求一个整数的倍数，倍数仅有0或1组成，且要尽可能小。 明明的问题可以归结为：任意给定一个自然数N，寻找一个M，要求M是N的倍数，且它的所有各位数字都是由0或1组成，并要求M尽可能小。

输入说明

你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据，每组测试数据仅占一行，每行仅包括一个正整数N（1≤N≤100），代表要求倍数的那个整数。每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

输出说明

对于每一组测试数据，你写的程序要求计算出一组相应的运算结果，并将这一组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。每组运算结果为一个整数，即N的倍数M。每组运算结果单独形成一行数据，其行首和行尾都没有任何空格，每组运算结果与其后一组运算结果之间没有任何空行，第一组运算结果前面以及最后一组运算结果后面也都没有任何空行。 注：通常，显示屏为标准输出设备。

#include<iostream>
using namespace std;
bool rate(int n)
{
	while (n)
	{
		if (n % 10 != 1 && n % 10 != 0)return 0;
		n /= 10;
	}
	return 1;
}
int main()
{
	int n;
	while (cin >> n)
	{
		for (int i = 1;; i++)
		{
			if (rate(i)&&i%n==0)
			{
				cout << i << endl; break;
			}
		}
	}
	return 0;

}

这里采取的是一一列举的方法，但如果你喜欢测试一下的话，你会发现99为什么跑不出来呢。这个代码之所以能过是因为 对于数值会很大的案例 测试用例中没有，所以可以枚举，但是如果有这个数呢，大家可以想想怎么办 我是采用的递归 但因为层数过多 re和tle.

递归思想

如果你只是想a了这道题 上面的方法已经够用了，

#include<iostream>
#include<math.h>
using namespace std;
//这个函数的整体思路为  比如 1 此时所有位数都是1 再大就是10 
//如果 10 不行 下一个找 11 若11不行 此时所有位数都是1 变为100
//然后 100不行 101 101不行 111 然后1000 大概这个思路
void shu(long long n,long long x=1)//x代表的就是 由0和1组成的数字。
{
	if (x % n == 0)
	{
		cout << x << endl;
		return;
	}
	//如果能除就return
	int len = 0;
	long long t = x;
	while (t)
	{
		if (t % 10 == 0)
		{
			x += pow(10, len);
			break;
		}
		t /= 10;
		len++;
	}//判断有没有位数上面还是0 如果还有 0 就给x 上面加上去1 
	if (t != 0)shu(n, x);
	//这里加一之后应该从新判断了于是递归
	else shu(n, pow(10, len));
	//如果全是1 就增加一位数 除了最高位都是0.

}
int main()
{
	long long n;
	while (cin >> n)
	{
		shu(n);
	}

}

这段代码不会全部ac 因为到了后面递归次数多了 虽然数据要比枚举少这是一定的 但是函数层层铺开占用的空间是很大的 所以使用于小的数据

思想见代码注释