所以,我有一个问题。
输入由两个数字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秒。
由于输入非常大,因此我显然不能使用模运算符。我当时在想按位运算符,但是那也不会让我受时间限制。有任何想法吗?谢谢!
最佳答案
好的,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