仅含0/1的N的最小倍数求解 组合分析与C代码TLE优化

本人是编程初学者，为提升能力正在在线判题平台刷题，目前遇到一道需用到组合分析的算法题，找到的同类解法无法适配到自己的代码中，需要组合分析思路的讲解。

题目描述 #

泡泡糖公主为证明自己的科研能力，通过糖果王国最棒的电脑BMO学习编程，和所有程序员一样，她爱上了二进制数。
出于对二进制数的痴迷，她喜爱形态类似二进制数的十进制数（即仅包含数字0和1的十进制数，例如101）。给定十进制数N，她需要找到N的一个形态类似二进制数的倍数，但哪怕借助BMO，部分数字的倍数查找也需要耗费极长时间。因沉迷解题她停下了所有工作，柠檬伯爵趁机占领了糖果王国。糖果王国的英雄芬恩和杰克无法对抗伯爵，也不懂倍数相关知识，因此求助找到符合要求的倍数以拯救王国。

输入要求 #

输入最多包含2*10^5行，每行一个整数N（0 < N < 10^{12），即需要查找非零倍数M对应的基准数，M必须仅由0、1组成且小于10}12，否则无法适配BMO的架构。

输出要求 #

每行输出一个整数，若存在多个符合要求的倍数则输出最小的那个，若无符合要求的解则输出-1，时间限制为2秒。

#include <stdlib.h>
#include <math.h>

int main() // normal ways works fine but i have to do it faster, time limit is 2s//
//doing 11 fors works to but its have same tle problem//
{
long long int n, R, num, res, expo;
int b = 0, dig[11] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, E=0, an, anmax = 1024, reseter, cob, casa;

while (E < 200000)
{
  E++;
  num = 0;
  scanf("%lld", &n); //I have to read a decimal number and from that found the smaller multiple number that is similar to a binary number, and cannot be 0//
  res=n%10;
  if ((res==1) || (res==0)) // in case the read number is already similar to binary, this works fine//
  { b=1;
    for ( num=n;((num>0) && (b==1)); num=num/10)
    {
      res=num%10;
      if ((res==1) || (res==0)){
      b=1;
      R=n;
      }else
      {
        b=0;
        R=-1;
      }
      
    }
    
    
  }else{
  if ((n > 0) && (n < 1000000000000))
  {
    if (n < 500000000000)
    {
      num = n;
      for (expo = -1; num >= 1; expo++, num = num / 10)//so expo is a varieble to found the smaller house of input to made a number, its just for reduce cycles//
      {
        res = num % 10;
      }
      if (res > 1)
      {
        expo = expo + 1;
      }
      dig[expo] = 1;
      R = ((dig[11] * 100000000000) + (dig[10] * 10000000000) + (dig[9] * 1000000000) + (dig[8] * 100000000) + (dig[7] * 10000000) + (dig[6] * 1000000) + (dig[5] * 100000) + (dig[4] * 10000) + (dig[3] * 1000) + (dig[2] * 100) + (dig[1] * 10) + (dig[0] * 1));
      for (dig[expo] = 1; ((expo < 11) && (b == 0)); expo++)//// 1 is fixed value until no one of numbers is divisible//
      {
        anmax = pow(2, expo);//forget this line//
        dig[expo] = 1;
        for (casa = 0; ((casa < expo) && (b == 0)); casa++)//here is my problem i dont know how to alternate all values that can be ninary// 
        { //this is my original idea to solve but this don't generate all possible values// 
          for (cob = 0; ((cob < 2) && (b == 0)); cob++)
          {
            dig[casa] = cob;
            R = ((dig[11] * 100000000000) + (dig[10] * 10000000000) + (dig[9] * 1000000000) + (dig[8] * 100000000) + (dig[7] * 10000000) + (dig[6] * 1000000) + (dig[5] * 100000) + (dig[4] * 10000) + (dig[3] * 1000) + (dig[2] * 100) + (dig[1] * 10) + (dig[0] * 1));
            if ((R % n) == 0)
            {
              b = 1;
            }
            
            
          }
        }
        if ((cob == 2) || (b==1))
        {
          for (reseter = expo; reseter >= 0; reseter--)//it works fine is just to start all values with 0 before its repeats//
          {
            dig[reseter] = 0;
          }
        }
      }
    }
    else
    {
      R = -1;
    }
    if((R==11111111111) && ((n!=21649) || (n!=513239))){
        R=-1; //its not important//
    }
  }else
  {
    R=-1;
  }
  
  }
  // reset para proximos valores//
  b = 0;
  printf("%lld\n", R);
}
return 0;
}

• 常规暴力枚举思路运行效率不足，编写11层循环枚举的方案同样会触发时间超限
• 当前枚举逻辑无法生成所有仅含0、1的候选数，多组输入下性能达不到2秒时间限制要求，需要基于正确的组合分析方法优化实现

首先做最基础的组合计数：所有满足「仅由0、1组成、非零、小于10^{12」的数，最高位固定为1，剩余最多11位每位可以选0或1，总数量只有2}12-2=4094个，这个候选集规模极小，完全不需要每组输入都重新枚举。
核心优化逻辑分两步：

1. 预生成所有合法候选数：用BFS从初始值1开始扩展，每次给当前数末尾分别拼接0和1，只要结果小于10^12就加入候选列表，这种生成方式天然按数值从小到大排列，不需要额外排序。
2. 查询处理：在线处理每组输入时，从小到大遍历预先生成的4094个候选数，找到第一个能被当前N整除的数就是答案，遍历完所有候选数都没有符合条件的就输出-1。
   这种方案总计算量极低：生成候选集仅需要四千余次操作，20万组查询每组平均只需要遍历数十个候选数就能得到结果，总操作量不到百万级，远低于2秒时间限制的承载能力。
   原有代码的性能瓶颈就在于每组查询都重复执行枚举逻辑，20万组的重复计算量被放大了几十万倍，自然会超时。另外原代码的数字位拼接逻辑有漏洞，没有覆盖所有0/1组合，才会出现漏候选数的问题。

补充剪枝：N大于10^12/2=5*1011时，它的最小正倍数是2N，必然大于等于10^12，直接返回-1即可，不需要遍历候选集。

内容的提问来源于stack exchange，提问作者Ntheus