在 Python 中查找 AP 中第一个为给定素数倍数的元素
pythonserver side programmingprogramming更新于 2025/10/10 6:36:17
假设我们有一个 AP 系列的第一项 (A) 和公差 (d),并且我们还有一个素数 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
ans := 1
x := x mod p
while y > 0,执行
如果 y AND 1 非零,则
ans :=(ans * x) mod p
y := y/2
x :=(x * x) mod p
返回 ans
从主方法中,执行以下操作 −
A := A mod P
D := D mod P
如果 A 与 0 相同,则
返回0
否则,当 D 与 0 相同时,则
返回 -1
否则,
X := get_pow(D, P - 2, P)
返回(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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

