Обернені#5213

Обернені (Розбір)

Оскільки число $n$ є простим, за малою теоремою Ферма виконується рівність

i^{n - 1} m o d n = 1 для будь - якого 1 \leq i < n

i^{n-1}~mod~n = 1~для~будь-якого~1 \le i < n

Цю рівність можна переписати у вигляді:

(i \cdot i^{n - 2}) m o d n = 1,

(i \cdot i^{n-2})~mod~n = 1,

звідки випливає, що оберненим до числа $i$ є число $j = i^{n - 2} m o d n$ j = i^{n-2}~mod~n.

Обернене число також можна знайти за допомогою розширеного алгоритму Евкліда. Розглянемо задачу пошуку числа $x$ , що задовольняє порівняння:

a x = 1 (m o d n)

ax = 1~(mod~n)

Це порівняння еквівалентне діофантовому рівнянню:

a x + n y = 1

ax + ny = 1

За допомогою розширеного алгоритму Евкліда знайдемо один з його розв'язків $(x_{0}, y_{0})$ (x_0, y_0). Тоді:

a x_{0} + n y_{0} = 1

ax_0 + ny_0 = 1

Розглянемо цю рівність за модулем $n$ . Отримаємо:

a x_{0} = 1 (m o d n)

ax_0 = 1~(mod~n)

Отже, число $x_{0}$ x_0 є оберненим до $a$ за модулем $n$ . Якщо значення $x_{0}$ x_0 від'ємне, необхідно додати до нього $n$ , щоб отримати число з діапазону $[1, n - 1]$ [1, n - 1].

Таким чином, в обох алгоритмах для кожного числа $i (1 \leq i < n)$ i~(1 \le i < n) пошук оберненого числа займає час $O (l o g_{2} n)$ O(log_2n). Отже, загальна асимптотична складність алгоритму становить $O (n l o g_{2} n)$ O(nlog_2n).

Розглянемо розв'язок з асимптотичною складністю $O (n)$ .

Теорема. Якщо $in v [i]$ — число, обернене до $i$ за модулем $n$ , то

in v [i] = - ⌊ \frac{n}{i} ⌋ \cdot in v [n m o d i] m o d n

inv[i] = - \left\lfloor \frac{n}{i} \right\rfloor \cdot inv[n~mod~i]~mod~n

Доведення. Відомо, що $n m o d i = n - ⌊ \frac{n}{i} ⌋ \cdot i$ n~mod~i = n - \left\lfloor \frac{n}{i} \right\rfloor \cdot i

Розглянемо цю рівність за модулем $n$ : $n m o d i = - ⌊ \frac{n}{i} ⌋ \cdot i m o d n$ n~mod~i = - \left\lfloor \frac{n}{i} \right\rfloor \cdot i~mod~n

Помножимо обидві частини рівності на $i^{- 1} \cdot (n m o d i)^{- 1}$ i^{-1} \cdot~(n~mod~i)^{-1}:

i^{- 1} \cdot (n m o d i)^{- 1} \cdot n m o d i = - ⌊ \frac{n}{i} ⌋ \cdot i \cdot i^{- 1} \cdot (n m o d i)^{- 1} m o d n

i^{-1} \cdot~(n~mod~i)^{-1} \cdot n~mod~i = - \left\lfloor \frac{n}{i} \right\rfloor \cdot i \cdot i^{-1} \cdot~(n~mod~i)^{-1}~mod~n

Після спрощення отримаємо:

i^{- 1} = - ⌊ \frac{n}{i} ⌋ \cdot (n m o d i)^{- 1} m o d n

i^{-1} = - \left\lfloor \frac{n}{i} \right\rfloor \cdot (n~mod~i)^{-1}~mod~n

Згідно з формулою, наведеною в теоремі, значення $in v [i]$ для кожного $i (1 \leq i < n)$ i~(1 \le i < n) може бути обчислене за час $O (1)$ . Отже, всі обернені елементи можна знайти за лінійний час $O (n)$ .

Приклад

Нехай $n = 5$ n = 5. Побудуємо таблицю обчислення обернених елементів:

Знайдемо обернені елементи, використовуючи формулу з теореми:

$in v [1] = 1$ inv[1] = 1 (базовий випадок)

$in v [2] == (- 2 \cdot in v [1]) m o d 5 = - 2 m o d 5 = 3$ inv[2] = = (-2 \cdot inv[1])~mod~5 = -2~mod~5 = 3

$in v [3] == (- 1 \cdot in v [2]) m o d 5 = - 3 m o d 5 = 2$ inv[3] = = (-1 \cdot inv[2])~mod~5 = -3~mod~5 = 2

$in v [4] == (- 1 \cdot in v [1]) m o d 5 = - 1 m o d 5 = 4$ inv[4] = = (-1 \cdot inv[1])~mod~5 = -1~mod~5 = 4

Реалізація алгоритму

Функція Pow повертає значення $x^{n} m o d m$ x^n~mod~m.

long long Pow(long long x, long long n, long long m)
{
  if (n == 0) return 1;
  if (n % 2 == 0) return Pow((x * x) % m, n / 2, m);
  return (x * Pow(x, n - 1, m)) % m;
}

Основна частина програми. Читаємо вхідне значення $n$ .

scanf("%d",&n);

Для кожного значення $i (1 \leq i < n)$ i~(1 \le i < n) виводимо обернений елемент за модулем $n$ , використовуючи формулу $i^{n - 2} m o d n$ i^{n-2}~mod~n.

for(i = 1; i < n; i++)
  printf("%lld ",Pow(i,n-2,n));
printf("\n");

Реалізація алгоритму – розширений алгоритм Евкліда

#include <stdio.h> 

int n, i, d, x, y;

void gcdext(int a, int b, int &d, int &x, int &y)
{
  if (b == 0)
  {
    d = a; x = 1; y = 0;
    return;
  }

  gcdext(b, a % b, d, x, y);

  int s = y;
  y = x - (a / b) * y;
  x = s;
}

int main(void)
{
  scanf("%d", &n);
  for (i = 1; i < n; i++)
  {
    // i * x + n * y = 1
    gcdext(i, n, d, x, y);
    if (x < 0) x += n;
    printf("%d ", x);
  }
  printf("\n");
  return 0;
}

C++

Реалізація алгоритму – лінійний розв'язок

Оголосимо масив $in v$ , в якому будемо зберігати обернені елементи:

in v [i] = i^{- 1} m o d n .

inv[i] = i^{-1}~mod~n.

#define MAX 1000001
int inv[MAX];

Читаємо вхідне значення $n$ .

scanf("%d", &n);

Обчислимо обернені елементи відповідно до формули з теореми.

inv[1] = 1;
for (i = 2; i <= n; i++)
  inv[i] = n - 1LL * (n / i) * inv[n % i] % n;

Виводимо відповідь.

for (i = 1; i < n; i++)
  printf("%d ", inv[i]);

Java реалізація

import java.util.*;
 
public class Main
{
  static long PowMod(long x, long n, long m)
  {
    if (n == 0) return 1;
    if (n % 2 == 0) return PowMod((x * x) % m, n / 2, m);
    return (x * PowMod(x, n - 1, m)) % m;
  }

  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    long n = con.nextLong();
    
    for(int i = 1; i < n; i++)
      System.out.print(PowMod(i,n-2,n) + " ");
    System.out.println();
    con.close();
  }
}

Java

Java реалізація – лінійний розв'язок

import java.util.*;

public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int inv[] = new int[n];
    
    inv[1] = 1;
    for (int i = 2; i < n; i++)
      inv[i] = (int) (n - 1L * (n / i) * inv[n % i] % n);
    
    for(int i = 1; i < n; i++)
      System.out.print(inv[i] + " ");
    System.out.println();
    con.close();
  }
}

Java

Python реалізація – лінійний розв'язок

Читаємо вхідне значення $n$ .

n = int(input())

Оголосимо список $in v$ , в якому будемо зберігати обернені елементи:

inv = [0 for _ in range(n + 1)]

Обчислимо обернені елементи відповідно до формули з теореми.

inv[1] = 1;
for i in range(2,n):
  inv[i] = n - (n // i) * inv[n % i] % n;

Виводимо відповідь.

for i in range(1,n):
  print(inv[i], end= " ")