任意给定一个正整数N，求一个最小的正整数M(M>1)，使得N*M的十进制表示形式里只含有1和0。...

这个问题可以通过模拟来解决。我们从M=2开始尝试，然后对于每个M，计算N*M的十进制表示形式，检查其是否只包含1和0。如果是，我们就找到了答案。否则，我们增加M的值并继续尝试，直到找到一个合适的M。

具体的实现步骤如下：

1. 初始化M=2。

2. 用一个while循环，检查N*M的十进制表示形式是否只包含1和0。如果是，返回M的值。

3. 如果N*M的十进制表示形式不是只包含1和0，将M的值加1，并继续循环。

下面是一个Python的实现示例：

def find_min_multiplier(n):
    m = 2
    while True:
        if set(str(n*m)) <= set(['0', '1']):
            return m
        m += 1

我们可以用这个函数来解决一个例子:

>>> find_min_multiplier(7)
142857

因为7*142857 = 999999，它的十进制表示形式只包含1和0。

相关问题

任意给定一个正整数N，求一个最小的正整数M(M>1)，使得N*M的十进制表示形式里只含有1和0。...C++BFS代码

以下是基于BFS的C++代码实现：

#include <iostream>
#include <queue>
#include <unordered_set>
using namespace std;

int minMultiple(int n) {
    queue<pair<int, int>> q;
    unordered_set<int> visited;

    q.push({1, 1});

    while (!q.empty()) {
        auto curr = q.front(); q.pop();
        int num = curr.first, steps = curr.second;

        if (num % n == 0) {
            return num;
        }

        if (visited.count(num % n) == 0) {
            visited.insert(num % n);

            q.push({num * 10, steps + 1});
            q.push({num * 10 + 1, steps + 1});
        }
    }

    return -1;
}

int main() {
    int n;
    cout << "Enter a positive integer: ";
    cin >> n;

    int res = minMultiple(n);

    if (res == -1) {
        cout << "Cannot find a multiple of " << n << " with only 1s and 0s." << endl;
    } else {
        cout << "The smallest multiple of " << n << " with only 1s and 0s is: " << res << endl;
    }

    return 0;
}

代码思路：

- 从1开始，每次将当前数字乘以10或者乘以10再加上1，然后模N，如果模N的结果为0，则当前数字就是所求的结果；
- 如果模N的结果没有出现过，则将其加入队列并标记为已访问，继续进行BFS；
- 如果队列为空但是没有找到符合条件的数字，则说明不存在这样的数字。

时间复杂度：$O(\frac{N}{\log N})$ （根据题目所给数据范围，实际运行时间很短）

给定两个正整数 n 和 k，求从 1到 n 这 n个正整数的十进制表示中 k 出现的次数。 输入格式 共一行，包含两个整数 n和 k。 输出格式 输出一个整数，表示答案。

算法1

暴力枚举每个数字的每一位，统计k出现的次数，时间复杂度为O(n*log_10(n))。

时间复杂度

参考文献

Python 代码

C++ 代码

算法2

统计k在每个数位上出现的次数，并累加得到最终答案。以k=3为例，假设当前处理的是x，x的第i位为di。有以下三种情况：

- di>k，则di可以取0~9中任意一个数字，共10^(i-1)种情况，其中i表示第i位，10^(i-1)表示该数位前(i-1)位共有10^(i-1)种情况。
- di<k，则第i位只能取0~di-1中的数字，如果i=1，则0不能出现，共di*(10^(i-1))种情况。
- di=k，则第i位只能取0~di-1中的数字，共(dk-1)*(10^(i-1)) + x%(10^(i-1))+1种情况，其中x%(10^(i-1))表示当前数位前(i-1)位的数字共有x%(10^(i-1))+1种情况，因为x前(i-1)位的数字可以取0~(x%(10^(i-1)))。

注意到以上三种情况中第一种情况和第二种情况可以合并成一个公式，故最终的公式为：

ans = ∑i=1 ^ len(n)[(n // (10^i))*10^(i-1)+min(max(n%(10^i)−k+1,0),10^(i−1))−(k==0)*10^(i−1)]
其中，n // (10^i)表示取n的前i位数字，max(n%(10^i)−k+1,0)表示取n的第i位数字时，能取到的范围。注意当k=0时，第二项需要减去10^(i-1)。

时间复杂度

参考文献

Python 代码

C++ 代码

算法3

对于每一位数位上出现k的次数进行统计。根据数位的不同分类具体处理，具体如下：

- 如果k=0，则枚举当前数位，次数为n/10^(i+1)*10^i，表示高位上数位1~n/10^(i+1)共可以变化10^i种，其中i表示数位从右数第x位，不包含本位（假设最低位为第0位）上的前缀0。

Python 代码

C++ 代码

- 如果当前位数字是k，则统计方式分为三种：

- 如果该位数字为0，则次数为前面数位（不包括本身）0~n/10^(i+1)的个数
- 如果该位数字不为0，则次数为前面数位（不包括本身）0~n/10^(i+1)的个数+1
- 如果i=0,即当前位为最低位且为k，则次数为1

Python 代码

C++ 代码

- 如果当前位数字小于k，则次数为前面数位（不包括本身）0~n/10^(i+1)的个数
- 如果当前位数字大于k，则次数为前面数位（不包括本身）0~n/10^(i+1)的个数+1
于是有以下代码

时间复杂度

参考文献

Python 代码

C++ 代码