Tərsinə çevrilmiş#5213

Tərsinə çevrilmiş (Həll təhlili)

$n$ ədədi sadə olduğu üçün Ferma-nın kiçik teoreminə əsasən aşağıdakı bərabərlik doğrudur

i^{n - 1} m o d n = 1 i s t ə ni l ə n 1 \leq i < n u ¨ c \c u ¨ n

i^{n-1}~mod~n = 1~istənilən~1 \le i < n~üçün

Bu bərabərliyi aşağıdakı şəkildə yenidən yazmaq olar:

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

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

buradan alınır ki, $i$ ədədinə tərs ədəd $j = i^{n - 2} m o d n$ j = i^{n-2}~mod~n ədədidir.

Tərs ədədi genişləndirilmiş Evklid alqoritmi vasitəsilə də tapmaq olar. Aşağıdakı müqayisəni ödəyən $x$ ədədinin tapılması məsələsinə baxaq:

a x = 1 (m o d n)

ax = 1~(mod~n)

Bu müqayisə aşağıdakı Diofant tənliyinə ekvivalentdir:

a x + n y = 1

ax + ny = 1

Genişləndirilmiş Evklid alqoritmi vasitəsilə onun həllərindən birini $(x_{0}, y_{0})$ (x_0, y_0) tapaq. Onda:

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

ax_0 + ny_0 = 1

Bu bərabərliyə $n$ modulu üzrə baxaq. Alırıq:

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

ax_0 = 1~(mod~n)

Deməli, $x_{0}$ x_0 ədədi $a$ -ya $n$ modulu üzrə tərs ədəddir. Əgər $x_{0}$ x_0 mənfi qiymət alırsa, onu $[1, n - 1]$ [1, n - 1] aralığından olan ədəd almaq üçün $n$ ilə toplamaq lazımdır.

Beləliklə, hər iki alqoritmdə hər bir $i (1 \leq i < n)$ i~(1 \le i < n) ədədi üçün tərs ədədin axtarılması $O (l o g_{2} n)$ O(log_2n) vaxt tələb edir. Deməli, alqoritmin ümumi asimptotik mürəkkəbliyi $O (n l o g_{2} n)$ O(nlog_2n) təşkil edir.

$O (n)$ asimptotik mürəkkəbliyə malik həllə baxaq.

Teorem. Əgər $in v [i]$ $i$ ədədinə $n$ modulu üzrə tərs ədəddirsə, onda

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

İsbat. Məlumdur ki, $n m o d i = n - ⌊ \frac{n}{i} ⌋ \cdot i$ n~mod~i = n - \left\lfloor \frac{n}{i} \right\rfloor \cdot i

Bu bərabərliyə $n$ modulu üzrə baxaq: $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

Bərabərliyin hər iki tərəfini $i^{- 1} \cdot (n m o d i)^{- 1}$ i^{-1} \cdot~(n~mod~i)^{-1}-ə vuraq:

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

Sadələşdirdikdən sonra alırıq:

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

Teoremdə verilmiş düsturə əsasən, hər bir $i (1 \leq i < n)$ i~(1 \le i < n) üçün $in v [i]$ qiyməti $O (1)$ vaxtda hesablana bilər. Deməli, bütün tərs elementləri xətti $O (n)$ vaxtda tapmaq mümkündür.

Misal

Tutaq ki, $n = 5$ n = 5. Tərs elementlərin hesablanması cədvəlini quraq:

Teoremdəki düsturdan istifadə edərək tərs elementləri tapaq:

$in v [1] = 1$ inv[1] = 1 (baza halı)

$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

Alqoritmin realizasiyası

Pow funksiyası $x^{n} m o d m$ x^n~mod~m qiymətini qaytarır.

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;
}

Proqramın əsas hissəsi. $n$ giriş qiymətini oxuyuruq.

scanf("%d",&n);

Hər bir $i (1 \leq i < n)$ i~(1 \le i < n) qiyməti üçün $i^{n - 2} m o d n$ i^{n-2}~mod~n düsturundan istifadə edərək $n$ modulu üzrə tərs elementi çap edirik.

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

Alqoritmin realizasiyası – genişləndirilmiş Evklid alqoritmi

#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++

Alqoritmin realizasiyası – xətti həll

Tərs elementləri saxlamaq üçün $in v$ massivini elan edək:

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

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

#define MAX 1000001
int inv[MAX];

$n$ giriş qiymətini oxuyuruq.

scanf("%d", &n);

Teoremdəki düstura uyğun olaraq tərs elementləri hesablayaq.

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

Cavabı çap edirik.

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

Java realizasiyası

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 realizasiyası – xətti həll

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 realizasiyası – xətti həll

$n$ giriş qiymətini oxuyuruq.

n = int(input())

Tərs elementləri saxlamaq üçün $in v$ siyahısını elan edək:

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

Teoremdəki düstura uyğun olaraq tərs elementləri hesablayaq.

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

Cavabı çap edirik.

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