1109 01组成的N的倍数
- 1 秒
- 131,072 KB
- 40 分
- 4 级题
给定一个自然数N，找出一个M，使得M > 0且M是N的倍数，并且M的10进制表示只包含0或1。求最小的M。
例如：N = 4，M = 100。
收起
输入
输入1个数N。(1 <= N <= 10^6)
输出
输出符合条件的最小的M。
输入样例
4
输出样例
100
因为只有0，1，显然可以用搜一下，然后考虑bfs，裸的bfs会MLE（感觉T倒是不会），接着考虑剪枝
首先我们可以知道，每次其实不用这一大段数计算的，我们只要每次保留这个数 % n 就可以，每次计算的时候直接计算他就可以，所以队列里只要存一个余数和我们答案的串就可以
然后再考虑，假如一个余数出现，比如3，会往3后面加0/1，那么如果后面余数在出来3，而且是在队列的后面，那他的大小肯定是要比前面出现的3大的，所以我们可以直接放弃这个3，不让他入队
注意要先加0，再加1，因为先找0，肯定是会小于1的，，如果先找1，找到余数为0的话，可能后面的0余数也为0，但是0比1小
例子：
217607
代码：
#include <bits/stdc++.h>
#include <time.h>
#define fi first
#define se second
using namespace std;typedef long long ll;
typedef double db;
int xx[4] = {1,-1,0,0};
int yy[4] = {0,0,1,-1};
const double eps = 1e-9;
typedef pair<int,int> P;
const int maxn = 2e6 + 5000;
const ll mod = 1e9 + 7;
//inline int sign(db a) { return a < -eps ? -1 : a > eps;}
//inline int cmp(db a,db b){ return sign(a - b);}
//ll mul(ll a,ll b,ll c) { ll res = 1; while(b) { if(b & 1) res *= a,res %= c; a *= a,a %= c,b >>= 1; } return res;}
//ll phi(ll x) { ll res = x; for(ll i = 2; i * i <= x; i++) { if(x % i == 0) res = res / i * (i - 1); while(x % i == 0) x /= i; } if(x > 1) res = res / x * (x - 1); return res;}
int fa[maxn];
int Find(int x) {if(x != fa[x]) return fa[x] = Find(fa[x]);return fa[x];
}
ll c,n,k;
queue<pair<string,int> >q;
string op[3] = {"0","1"};
int vis[maxn];
int main() {ios::sync_with_stdio(false);while(cin >> n) {memset(vis,0,sizeof(vis));q.push(make_pair("1",1));while(!q.empty()) {pair<string,int> p = q.front();q.pop();
// cout << p.first << endl;if(p.second == 0) {cout << p.first << endl;return 0;}for(int i = 0; i < 2; i++) {string strr = p.first + op[i];int y = p.second * 10 + (op[i][0] - '0');int x = y % n;
// cout << x << endl;if(!vis[x]) {q.push(make_pair(strr,x));vis[x] = 1;}}}}cerr << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}