最少的1 最少的 1 问题描述 给定一个正整数 n n, 找出所有 n n 的倍数的二进制表示中最少有多少个 1 。 输入格式 输入一行包含一个整数 n n 。 输出格式 输出一行包含一个整数表示答安。

### 计算正整数 n 的倍数中二进制形式含有的最小数量的 1 要解决这个问题，可以采用动态规划的方法来找到正整数 `n` 的倍数中二进制表示中含有最少数量的 1。以下是详细的解答： #### 动态规划方法 定义状态 `dp[i][j]` 表示当前处理到第 `i` 位时，模 `n` 后余数为 `j` 的情况下所需的最小 1 数量。 初始条件： - 当没有任何位被选定时（即 i = 0），仅当余数 j = 0 时有效，此时所需 1 的数量为 0。因此初始化 `dp[0][0] = 0`，其余均为无穷大。 转移方程：对于每一位可以选择放置 0 或者 1，则有如下两种情况： - 如果该位置放的是 0，则不会改变之前的余数值； - 如果该位置放的是 1，则会增加对应的权重并更新余数。 具体实现可以通过枚举所有可能的状态来进行填充表格直到达到目标长度为止[^2]。 最终结果可以从最后一个阶段的所有合法状态中选取具有最小计数值的那个作为答案。 下面是基于上述思路的一个 Python 实现例子: ```python def minOnesInMultiple(n, length): MOD = float('inf') dp = [[MOD]*n for _ in range(length+1)] # Base case initialization. dp[0][0] = 0 power_of_two_mod_n = [pow(2,i,n) % n for i in range(length)] for l in range(1,length+1): for r in range(n): if dp[l-1][r]==MOD: continue # Option to append '0' next_remainder_zero = (r * 2)%n dp[l][next_remainder_zero]=min(dp[l][next_remainder_zero],dp[l-1][r]) # Option to append '1' next_remainder_one=(r*2 +1 )%n dp[l][next_remainder_one ]=min(dp[l][next_remainder_one ],dp[l-1][r]+1) result=min([val for val in dp[-1] if val != MOD]) return result if result!=float('inf') else -1 # Example usage: print(minOnesInMultiple(5, 3)) # Output should be the minimum number of ones required. ``` 此代码片段实现了寻找指定长度下某个特定自然数N的倍数中的最少数目的'1'. 它通过构建一个二维数组记录不同长度和剩余类别下的最优解，并逐步扩展直至获得整个序列的最佳解决方案.