ধরা যাক একটি AP সিরিজের প্রথম টার্ম (A) এবং কমন ডিফারেন্স (d) দেওয়া আছে, এবং একটি প্রাইম নম্বর P। আমাদের AP-এ সেই প্রথম উপাদানের পজিশন বের করতে হবে যা P-এর গুণিতক।
ইনপুট: A=3, D=4, P=5 → আউটপুট 3 (চতুর্থ টার্ম 15 যা 5-এর গুণিতক: 3, 7, 11, 15)।
সমাধানের ধাপসমূহ (মডুলার অ্যরিথমেটিক + ফার্মাস লিটল থিওরেম)
- get_pow(x, y, p): মডুলার এক্সপোনেনশিয়েশন (x^y mod p)
- মেইন ফাংশন get_nearest(A, D, P):
- A %= P; D %= P
- যদি A==0: return 0
- যদি D==0: return -1
- অন্যথায়: X = get_pow(D, P-2, P) (মডুলার ইনভার্স); return (X * (P - A)) % P
উদাহরণ
def get_pow(x, y, p):
ans = 1
x = x % p
while y > 0:
if y & 1:
ans = (ans * x) % p
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
