สมมุติว่าเรามีพจน์แรก (A) และผลต่างร่วม (d) ของอนุกรม AP และเรายังมีจำนวนเฉพาะ P ด้วย เราต้องหาตำแหน่งขององค์ประกอบแรก ใน AP ที่กำหนด ซึ่งเป็นผลคูณของจำนวนเฉพาะที่ระบุ P.
ดังนั้น หากอินพุตเป็น A =3, D =4, P =5 เอาต์พุตจะเป็น 3 เนื่องจากพจน์ที่สี่ของ AP ที่กำหนดคือผลคูณของจำนวนเฉพาะ 5 ดังนั้น เทอมแรก =3 เทอมที่สอง =3+4 =7, เทอมที่สาม =3+2*4 =11 และเทอมที่สี่ =3+3*4 =15.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน get_pow() นี่จะใช้เวลา x, y, p
-
ตอบ :=1
-
x :=x mod p
-
ในขณะที่ y> 0 ทำ
-
ถ้า y และ 1 ไม่ใช่ศูนย์ ดังนั้น
-
ans :=(ans * x) mod p
-
-
y :=y/2
-
x :=(x * x) mod p
-
-
กลับมาอีกครั้ง
-
จากวิธีหลัก ให้ทำดังนี้ −
-
A :=ตัวดัดแปลง P
-
D :=D mod P
-
ถ้า A เท่ากับ 0 แล้ว
-
คืนค่า 0
-
-
มิฉะนั้นเมื่อ D เท่ากับ 0 แล้ว
-
กลับ -1
-
-
มิฉะนั้น
-
X :=get_pow(D, P - 2, P)
-
return(X *(P - A)) mod P
-
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def get_pow(x, y, p) : ans = 1 x = x % p while y > 0 : if y & 1 : ans = (ans * x) % p y = y >> 1 x = (x * x) % p return ans def get_nearest(A, D, P) : A %= P D %= P if A == 0 : return 0 elif D == 0 : return -1 else : X = get_pow(D, P - 2, P) return (X * (P - A)) % P A = 3 D = 4 P = 5 print(get_nearest(A, D, P))
อินพุต
A = 3 D = 4 P = 5
ผลลัพธ์
3
