Мультипликативный порядок
В теории чисел, учитывая целое число A и положительное целое число N с НОД (A, N) = 1, мультипликативный порядок по модулю N - это наименьшее положительное целое число k с A ^ k (mod N) = 1. (0 < К <N)
Примеры :
Ввод: A = 4, N = 7 Выход: 3 объяснение: НОД (4, 7) = 1 A ^ k (mod N) = 1 (наименьшее положительное целое число K) 4 ^ 1 = 4 (мод 7) = 4 4 ^ 2 = 16 (мод 7) = 2 4 ^ 3 = 64 (мод 7) = 1 4 ^ 4 = 256 (мод 7) = 4 4 ^ 5 = 1024 (мод 7) = 2 4 ^ 6 = 4096 (мод 7) = 1 наименьшее натуральное число K = 3 Ввод: A = 3, N = 1000. Вывод: 100 (3 ^ 100 (mod 1000) == 1) Ввод: A = 4, N = 11 Выход: 5
Если мы внимательно рассмотрим, то увидим, что нам не нужно каждый раз рассчитывать мощность. мы можем получить следующую степень, умножив «А» на предыдущий результат модуля.
Объяснение : А = 4, N = 11 исходный результат = 1 с нормальным с модульной арифметикой (результат A *) 4 ^ 1 = 4 (мод. 11) = 4 || 4 * 1 = 4 (мод. 11) = 4 [результат = 4] 4 ^ 2 = 16 (мод 11) = 5 || 4 * 4 = 16 (мод. 11) = 5 [результат = 5] 4 ^ 3 = 64 (мод. 11) = 9 || 4 * 5 = 20 (мод. 11) = 9 [результат = 9] 4 ^ 4 = 256 (мод. 11) = 3 || 4 * 9 = 36 (мод. 11) = 3 [результат = 3] 4 ^ 5 = 1024 (мод. 5) = 1 || 4 * 3 = 12 (мод. 11) = 1 [результат = 1] наименьшее натуральное число 5
Run a loop from 1 to N-1 and Return the smallest +ve power of A under modulo n which is equal to 1.
Below is the implementation of above idea.
CPP
// C++ program to implement multiplicative order #include<bits/stdc++.h> using namespace std; // function for GCD int GCD ( int a , int b ) { if (b == 0 ) return a; return GCD( b , a%b ) ; } // Fucnction return smallest +ve integer that // holds condition A^k(mod N ) = 1 int multiplicativeOrder( int A, int N) { if (GCD(A, N ) != 1) return -1; // result store power of A that rised to // the power N-1 unsigned int result = 1; int K = 1 ; while (K < N) { // modular arithmetic result = (result * A) % N ; // return samllest +ve integer if (result == 1) return K; // increment power K++; } return -1 ; } //driver program to test above function int main() { int A = 4 , N = 7; cout << multiplicativeOrder(A, N); return 0; } |
Java
// Java program to implement multiplicative order import java.io.*; class GFG { // function for GCD static int GCD( int a, int b) { if (b == 0 ) return a; return GCD(b, a % b); } // Function return smallest +ve integer that // holds condition A^k(mod N ) = 1 static int multiplicativeOrder( int A, int N) { if (GCD(A, N) != 1 ) return - 1 ; // result store power of A that rised to // the power N-1 int result = 1 ; int K = 1 ; while (K < N) { // modular arithmetic result = (result * A) % N; // return samllest +ve integer if (result == 1 ) return K; // increment power K++; } return - 1 ; } // driver program to test above function public static void main(String args[]) { int A = 4 , N = 7 ; System.out.println(multiplicativeOrder(A, N)); } } /* This code is contributed by Nikita Tiwari.*/ |
Python3
# Python 3 program to implement # multiplicative order # funnction for GCD def GCD (a, b ) : if (b = = 0 ) : return a return GCD( b, a % b ) # Fucnction return smallest + ve # integer that holds condition # A ^ k(mod N ) = 1 def multiplicativeOrder(A, N) : if (GCD(A, N ) ! = 1 ) : return - 1 # result store power of A that rised # to the power N-1 result = 1 K = 1 while (K < N) : # modular arithmetic result = (result * A) % N # return samllest + ve integer if (result = = 1 ) : return K # increment power K = K + 1 return - 1 # Driver program A = 4 N = 7 print (multiplicativeOrder(A, N)) # This code is contributed by Nikita Tiwari. |
C#
// C# program to implement multiplicative order using System; class GFG { // function for GCD static int GCD( int a, int b) { if (b == 0) return a; return GCD(b, a % b); } // Function return smallest +ve integer // that holds condition A^k(mod N ) = 1 static int multiplicativeOrder( int A, int N) { if (GCD(A, N) != 1) return -1; // result store power of A that // rised to the power N-1 int result = 1; int K = 1; while (K < N) { // modular arithmetic result = (result * A) % N; // return samllest +ve integer if (result == 1) return K; // increment power K++; } return -1; } // Driver Code public static void Main() { int A = 4, N = 7; Console.Write(multiplicativeOrder(A, N)); } } // This code is contributed by Nitin Mittal. |
PHP
<?php // PHP program to implement // multiplicative order // function for GCD function GCD ( $a , $b ) { if ( $b == 0 ) return $a ; return GCD( $b , $a % $b ) ; } // Fucnction return smallest // +ve integer that holds // condition A^k(mod N ) = 1 function multiplicativeOrder( $A , $N ) { if (GCD( $A , $N ) != 1) return -1; // result store power of A // that rised to the power N-1 $result = 1; $K = 1 ; while ( $K < $N ) { // modular arithmetic $result = ( $result * $A ) % $N ; // return samllest +ve integer if ( $result == 1) return $K ; // increment power $K ++; } return -1 ; } // Driver Code $A = 4; $N = 7; echo (multiplicativeOrder( $A , $N )); // This code is contributed by Ajit. ?> |
Javascript
<script> // JavaScript program to implement // multiplicative order // function for GCD function GCD(a, b) { if (b == 0) return a; return GCD(b, a % b); } // Function return smallest +ve integer that // holds condition A^k(mod N ) = 1 function multiplicativeOrder(A, N) { if (GCD(A, N) != 1) return -1; // result store power of A that rised to // the power N-1 let result = 1; let K = 1; while (K < N) { // modular arithmetic result = (result * A) % N; // return samllest +ve integer if (result == 1) return K; // increment power K++; } return -1; } // Driver Code let A = 4, N = 7; document.write(multiplicativeOrder(A, N)); // This code is contributed by chinmoy1997pal. </script> |
Выход :
3
Сложность времени: O (N)
Ссылка: https://en.wikipedia.org/wiki/Multiplicative_order
Эта статья предоставлена Нишантом Сингхом. Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.
Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .