Giả sử chúng ta có một số A. Chúng ta phải tạo một số lớn X bằng cách ghép A, n lần liên tiếp và tìm giá trị của X modulo m.
Vì vậy, nếu đầu vào là A =15 n =3 m =8, thì đầu ra sẽ là 3, vì số x sẽ là 151515 và 151515 mod 8 =3.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- nếu A giống 0, thì
- trả về 0
- an:=A
- c:=số chữ số trong A
- c:=10 ^ c
- d:=c-1
- newmod:=d * m
- val:=(c ^ n mod newmod) -1
- val:=(val + newmod) mod newmod
- an:=(an * val) mod newmod
- tầng trả lại của (an / d)
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def solve(A, n, m):
if A == 0:
return 0
an=A
c=len(str(A))
c=10**c
d=c-1
newmod = d*m
val = pow(c,n,newmod)-1
val = (val+newmod) % newmod
an = (an*val) % newmod
return an // d
A = 15
n = 3
m = 8
print(solve(A, n, m)) Đầu vào
15, 3, 8
Đầu ra
3