c++ - 鸽子洞/多个数字

Question

input : integer ( i'll call it N ) and (1 <= N <= 5,000,000 )
output : integer, multiple of N and only contains 0,7 

Ex.
Q1 input : 1 -> output : 7 ( 7 mod 1 == 0 )
Q2 input : 2 -> output : 70  ( 70 mod 2 == 0 )

#include <string>
#include <iostream>

using namespace std;

typedef long long ll;

int remaind(string num, ll m)
{
    ll mod = 0;
    for (int i = 0; i < num.size(); i++) {
        int digit = num[i] - '0';
        mod = mod * 10 + digit;
        mod = mod % m;
    }
    return mod;
}



int main()
{
    int n;
    string ans;
    cin >> n;
    ans.append(n, '7');
    for (int i = ans.length() - 1; i >= 0; i--)
    {
        if (remaind(ans, n) == 0)
        {
            cout << ans;
            return 0;
        }
        ans.at(i) = '0';
    }
    return 0;
}

有没有办法降低时间复杂度？

我只是非常努力地尝试，当 n 超过 1000000 时，它需要更多的时间来运行

附言。更改代码PS2。由于代码错误再次更改代码PS3。再次优化代码PS4。重写帖子

Answer 1

您的方法是错误的，假设您将“70”除以 5。那么您的结果将是 2，这是不正确的(只需分析您的代码以了解为什么会发生这种情况)。

您确实可以根据 77777770000000 之类的数字进行搜索，但请多考虑一下 - 哪些数字需要加零，哪些数字不需要加零。

接下来，不要使用字符串!如果您知道 a 的提醒和 b 的提醒，请考虑 a * b 的提醒。编程时，请注意整数大小，使用 64 位整数。

现在，a + b 呢？

最后，找到数字 10、100、1000、10000 等的提醒(再一次，不要使用字符串，仍然尝试找到 10 的任意次方的提醒)。

好吧，如果你做到了所有这些，你将能够轻松解决整个问题。