Теория чисел | Генераторы конечной циклической группы при сложении

Опубликовано: 19 Января, 2022

Дано число n, найти все образующие циклической аддитивной группы по модулю n. Генератор набора {0, 1,… n-1} - это такой элемент x, что x меньше n, и с помощью x (и операции сложения) мы можем сгенерировать все элементы набора.
Примеры:

 Ввод: 10
Выход: 1 3 7 9
Создаваемый набор: {0, 1, .. 9}
Добавляя 1, один или несколько раз, мы 
может создавать все элементы от 0 до 9.
Аналогично, используя 3, мы можем сгенерировать все
элементы.
30% 10 = 0, 21% 10 = 1, 12% 10 = 2, ...
То же самое верно для 7 и 9.

Ввод: 24
Выход: 1 5 7 11 13 17 19 23

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

A simple solution is to run a loop from 1 to n-1 and for every element check if it is generator. To check generator, we keep adding element and we check if we can generate all numbers until remainder starts repeating.
An Efficient solution is based on the fact that a number x is generator if x is relatively prime to n, i.e., gcd(n, x) =1.
Below is the implementation of above approach:

C++

// A simple C++ program to find all generators
#include <bits/stdc++.h>
using namespace std;
 
// Function to return gcd of a and b
int gcd(int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b%a, a);
}
 
// Print generators of n
int printGenerators(unsigned int n)
{
    // 1 is always a generator
    cout << "1 ";
 
    for (int i=2; i < n; i++)
 
        // A number x is generator of GCD is 1
        if (gcd(i, n) == 1)
            cout << i << " ";
}
 
// Driver program to test above function
int main()
{
    int n = 10;
    printGenerators(n);
    return 0;
}

Java

// A simple Java program to find all generators
 
class GFG {
     
 
// Function to return gcd of a and b
static int gcd(int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b%a, a);
}
 
// Print generators of n
static void printGenerators(int n)
{
    // 1 is always a generator
    System.out.println("1 ");
 
    for (int i=2; i < n; i++)
 
        // A number x is generator of GCD is 1
        if (gcd(i, n) == 1)
            System.out.println(i +" ");
}
 
// Driver program to test above function
public static void main(String args[])
{
    int n = 10;
    printGenerators(n);
}
}

Python3

# Python3 program to find all generators
 
# Function to return gcd of a and b
def gcd(a, b):
    if (a == 0):
        return b;
    return gcd(b % a, a);
 
# Print generators of n
def printGenerators(n):
     
    # 1 is always a generator
    print("1", end = " ");
 
    for i in range(2, n):
 
        # A number x is generator
        # of GCD is 1
        if (gcd(i, n) == 1):
            print(i, end = " ");
 
# Driver Code
n = 10;
printGenerators(n);
     
# This code is contributed by mits

C#

// A simple C# program to find all generators
using System;
 
class GFG
{
     
// Function to return gcd of a and b
static int gcd(int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
 
// Print generators of n
static void printGenerators(int n)
{
    // 1 is always a generator
    Console.Write("1 ");
 
    for (int i = 2; i < n; i++)
 
        // A number x is generator of GCD is 1
        if (gcd(i, n) == 1)
            Console.Write(i +" ");
}
 
// Driver code
public static void Main(String []args)
{
    int n = 10;
    printGenerators(n);
}
}
 
// This code contributed by Rajput-Ji

PHP

<?php
// PHP program to find all generators
 
// Function to return gcd of a and b
 
function gcd($a, $b)
{
    if ($a == 0)
        return $b;
    return gcd($b % $a, $a);
}
 
// Print generators of n
function printGenerators($n)
{
     
    // 1 is always a generator
    echo "1 ";
 
    for ($i = 2; $i < $n; $i++)
 
        // A number x is generator
        // of GCD is 1
        if (gcd($i, $n) == 1)
            echo $i, " ";
}
 
// Driver program to test
// above function
    $n = 10;
    printGenerators($n);
     
// This code is contributed by Ajit
?>

Javascript

<script>
 
// A simple Javascript program to
// find all generators
 
// Function to return gcd of a and b
function gcd(a, b)
{
    if (a == 0)
        return b;
         
    return gcd(b % a, a);
}
 
// Print generators of n
function printGenerators(n)
{
     
    // 1 is always a generator
    document.write("1 ");
 
    for(var i = 2; i < n; i++)
 
        // A number x is generator of
        // GCD is 1
        if (gcd(i, n) == 1)
            document.write(i + " ");
}
 
// Driver Code
var n = 10;
 
printGenerators(n);
 
// This code is contributed by Kirti
 
</script>

Выход :

 1 3 7 9

Как это работает?
Если мы рассмотрим все остатки от n последовательных кратных x, то некоторые остатки будут повторяться, если НОД x и n не равно 1. Если некоторые остатки повторяются, то x не может быть генератором. Обратите внимание, что после n последовательных кратных остатков остатки все равно будут повторяться.
Интересное наблюдение:
Количество образующих числа n равно Φ (n), где Φ - функция Эйлера Totient.
Эта статья предоставлена Ujjwal Goyal . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Misc

Теория чисел | Генераторы конечной циклической группы при сложении

C++

Java

Python3

C#

PHP

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ