1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#!/usr/bin/env python3
TESTS = [
[12, 3, 8],
[2, 15, 17],
[456, 6, 1296],
[1234, 100, 9],
[11223344, 1000000, 142857],
[55667788, 10000000, 1000000007],
[1357, 24682468, 999999999],
[24680, 1357913579, 777777777],
[998, 1000000000000, 999],
[1234, 11111111111111, 30],
[1, 222222222222222, 123456789],
[2016, 666666666666666, 8888888888],
[11223344, 555666777888999, 1357924680],
[999999999999999967, 999999999999999877, 999999999999999989],
[123456789123456789, 123456789123456789, 987654321123456789]
]
def powmod(a, n, m):
if n == 1:
return a % m
if n % 2:
return powmod(a, n // 2, m) ** 2 * a % m
return powmod(a, n // 2, m) ** 2 % m
# Gọi l là "chiều dài" của x, l = int(log10(x) + 1) hay l = len(str(x))
# Đặt l ** 10 = a, dễ thấy y = x * (a**(n-1) + a**(n-2) + ... + a + 1)
# = x * (a**n - 1) / (a - 1)
# y chia m bằng k dư q hay x * (a**n - 1) / (a - 1) = k * m + q
# <=> x * (a**n - 1) = k * (a*m - a) + q * (a - 1)
# <=> q = x * (a**n - 1) % (a*m - a) / (a - 1)
with open('REMAINDER.TXT', 'w') as f:
for case in TESTS:
a = 10 ** len(str(case[0]))
case[2] *= a - 1
p = powmod(a, case[1], case[2])
f.write(str(case[0] * (p - 1) % case[2] // (a - 1)) + '\n')
|
