BFS 或 同余模定理(poj 1426)

时间:2021-10-03 08:51:39

题目:Find The Multiple

题意:求给出的数的倍数,该倍数是只由 1与 0构成的10进制数。

思路:nonzero multiple  非零倍数  啊。

   英语弱到爆炸,理解不了题意。。。。。

   STL 在c++过不了,  一直TLE,

   最后只好看了下大神的代码。

#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set> #define c_false ios_base::sync_with_stdio(false); cin.tie(0)
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define zero_(x,y) memset(x , y , sizeof(x))
#define zero(x) memset(x , 0 , sizeof(x))
#define MAX(x) memset(x , 0x3f ,sizeof(x))
#define swa(x,y) {LL s;s=x;x=y;y=s;}
using namespace std ;
#define N 50005
const double PI = acos(-1.0);
typedef long long LL ;
LL n;
LL cal(LL n){
queue <LL> s;
LL pos = , x;
s.push(pos);
while(){
pos = s.front();
for(LL i = ; i<; i++){
x = pos * + i;
if(x%n == ) return x;
s.push(x);
}
s.pop();
}
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(~scanf("%I64d", &n) && n){
if(n == ) {
printf("%I64d\n", n);
continue;
}
printf("%I64d\n", cal(n));
}
return ;
}

还有种使用模运算的:

(a*b)%n = (a%n *b%n)%n

(a+b)%n = (a%n +b%n)%n

http://blog.csdn.net/lyy289065406/article/details/6647917