HDU 2847 Binary String 给定二进制n与整数k，插入0/1使得n能整除k，求最小的解 - c++编程基础

题意：

给定二进制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)