Pythonで指定されたPrimeの倍数であるAPの最初の要素を検索します

APシリーズの第1項（A）と共通の差（d）があり、素数Pもあるとすると、最初の要素の位置を見つける必要があります。与えられた素数Pの倍数である与えられたAPで。

したがって、入力がA =3、D =4、P =5の場合、指定されたAPの第4項は素数5の倍数であるため、出力は3になります。したがって、第1項=3、第2項=3 + 4 =7、第3項=3 + 2 * 4=11および第4項=3+ 3 *4=15。

これを解決するには、次の手順に従います-

• 関数get_pow（）を定義します。これにはx、y、pが必要です

• ans：=1

• x：=x mod p

• 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）

  • 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