所以,我有一个问题。

输入由两个数字NM组成。 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秒。

由于输入非常大,因此我显然不能使用模运算符。我当时在想按位运算符,但是那也不会让我受时间限制。有任何想法吗?谢谢!

最佳答案

好的,NetVipeC的答案很快变丑了

该答案基于三个身份

x(1) = 1
x(n) = x(n-1) * 10 + 1
x(2n) = x(n)*(x(n)*9 + 2)


这些也保留Z_M。

我将这些身份自下而上地编写,但由于实现起来非常简单,因此其实现自上而下。

#include <stdio.h>

long long modulo(long long n, long long m) {
    if (n == 1) return 1;
    long long mod = modulo(n / 2, m);
    long long whole = ((mod * 9 + 2) * mod) % m;
    if(n & 1)
        return (whole * 10 + 1) % m;
    return whole;
}

int main() {
    printf("%ld\n", modulo(3, 3));
    printf("%ld\n", modulo(4, 7));
    printf("%ld\n", modulo(5, 18));
    printf("%ld\n", modulo(1e6, 123456789));
    printf("%ld\n", modulo(1e15, 123456789));
}


输出:

time ./tst
0
5
5
1239742
93889873
./tst  0.00s user 0.00s system 56% cpu 0.002 total

09-05 18:20
查看更多