HDU 2847 Binary String 給定二進制n與整數k，插入0/1使得n能整除k，求最小的解

題意：

給定二進制n與整數k

允許在任意位置插入0/1使得n能整除k

求最小的解

顯然這樣的n一定存在，且k<=200，n<= (1<<20)，所以在 1<<28 內一定有解

思路：

首先是 x*k一定是 k 的倍數

所以枚舉 x = 1 -> 正無窮

若 字符串s 能構造成 x*k 則說明x*k是一個解
且此時x最小，即 x*k是最小解

構造過程是

先把x*k變成一個二進制字符串 t

1、若s中的 0 和 1 個數還比 t多，那麼一定是不可構造的 2、若s 與 t 的最長公共序列 長度 = strlen(s)，則說明s 是t 的不連續子串 ，即 t 能構造出來

而這裡的最長公共序列長度特殊，O(n)就可以算出了

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define ll __int64
ll n, m, k;
char s[40], t[40];
void go(ll x, char *S){
	ll top = 1;
	while(x){ S[top++] = ('0'+(x&1));	x>>=1;	}
	S[top] = 0;
}
ll z, o;//n中0 1個數
ll Zero(ll x){ll ans = 0; while(x){ans += !(x&1);x>>=1;}return ans;}
ll One(ll x){ll ans = 0; while(x){ans += (x&1);x>>=1;}return ans;}
ll work(char *c){
	ll ans = 0, er = 1;
	for(ll i = strlen(c)-1; i>=0; i--, er<<=1)if(c[i]=='1')ans += er;
	return ans;
}
bool ok(ll x){
	if(Zero(x)