สมมติว่าเรามีตัวเลข A เราต้องสร้าง X จำนวนมากโดยเชื่อม A, n ครั้งติดต่อกันแล้วหาค่าของ X modulo m
ดังนั้น หากอินพุตเป็น A =15 n =3 m =8 เอาต์พุตจะเป็น 3 เพราะตัวเลข x จะเป็น 151515 และ 151515 mod 8 =3
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ถ้า A เท่ากับ 0 แล้ว
- คืน 0
- อัน:=เอ
- c:=จำนวนหลักใน 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 ใหม่
- ชั้นกลับของ (an / d)
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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)) อินพุต
15, 3, 8
ผลลัพธ์
3
