c - 使用分而治之的方法

Question

所以，我有一个问题。

输入由两个数字N和M组成。 N 基本上告诉我们将出现的 1 的数量，而 M 是我们除以该数字并返回余数的数字。

1≤N≤10^16
2≤M≤10^9

Sample input:
3 3
4 7
5 18

Sample output:
0
5   
5

说明:

111 % 3 = 0
1111 % 7 = 5
11111%18 = 5 

时间限制:最多 1 秒。

由于输入非常大，我显然无法使用模运算符。我正在考虑按位运算符，但这也不会让我在时间限制内。有任何想法吗？谢谢!

Answer 1

我希望这不是 Project Euler 或其他类似的网站。

首先，数字 1111... 被命名为 Repunit 。

modular arithmetic 状态:

如果a1 = b1 mod n并且a2 = b2 mod n那么:

a1 + a2 = b1 + b2 mod n
a1 - a2 = b1 - b2 mod n
a1 * a2 = b1 * b2 mod n

大小 n 的 Repunits 可以用基数 10 写成:1*10^n + 1*10^(n-1) ... + 1*10 + 1 .

这将是1*10^n + 1*10^(n-1) ... + 1*10 + 1 = X mod n

1 = x1 mod n
x1*10 + 1 = x2 mod n
x2*10 + 1 = x3 mod n
...
x(n-1)*10 + 1 = X mod n

最后的模块化结果将是解决方案:

C++ 代码，由 Steve Cox 提议更新代码:

#include <iostream>
#include <map>
#include <cmath>

long long repunit_module(long long repunit_size, long long n) {
    if (repunit_size < 100) {
        // Calculate normally
        long long module_value = 1;
        for (long long i = 2; i <= repunit_size; i++) {
            module_value = (module_value * 10 + 1) % n;
        }
        return module_value;
    } else {
        // x(2n) = (x(n+1) - x(n) + 1) * x(n)
        long long xn = repunit_module(repunit_size / 2, n); // x(n) mod n
        long long xn1 = (xn * 10 + 1) % n; // x(n+1) mod n
        long long rest = xn1 - xn + 1; 
        if (rest < 0) // normalyze for module
            rest += n;
        long long result = ((rest % n) * xn) % n;

        if (repunit_size % 2 == 1) { // if size is 2n + 1 calc the last
            return (result * 10 + 1) % n;
        } else { // if size is 
            return result;
        }
    }    
}

int main() {
    long long rps = std::pow(10, 16);
    std::cout << repunit_module(3, 3) << std::endl;
    std::cout << repunit_module(4, 7) << std::endl;
    std::cout << repunit_module(5, 18) << std::endl;
    std::cout << repunit_module(rps, 123456789) << std::endl;
}