Рубрики

Подсчитать количество решений x ^ 2 = 1 (mod p) в заданном диапазоне

По двум целым числам n и p найти число интегральных решений для x 2 = 1 (mod p) на отрезке [1, n].

Примеры:

Input : n = 10, p = 5
Output : 4
There are four integers that satisfy the equation
x2 = 1. The numbers are 1, 4, 6 and 9.

Input : n = 15, p = 7
Output : 5
There are five integers that satisfy the equation
x2 = 1. The numbers are 1, 8, 15, 6 and 13.  

Одно простое решение — пройти все числа от 1 до n. Для каждого числа проверьте, удовлетворяет ли оно уравнению. Мы можем избежать прохождения всего диапазона. Идея основана на том факте, что если число x удовлетворяет уравнению, то все числа вида x + i * p также удовлетворяют уравнению. Мы перебираем все числа от 1 до p и для каждого числа x, удовлетворяющего уравнению, находим количество чисел вида x + i * p. Чтобы найти число, мы сначала находим наибольшее число для данного x и затем добавляем (наибольший номер — x) / p к результату.

Ниже приведена реализация идеи.

C ++

// C ++ программа для подсчета количества значений
// которые удовлетворяют x ^ 2 = 1 mod p, где x лежит
// в диапазоне [1, n]
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

  

int findCountOfSolutions(int n, int p)

{

    // Инициализировать результат

    ll ans = 0;

  

    // Обходим все числа меньше чем

    // заданный номер р. Обратите внимание, что мы не

    // переход от 1 до n, но от 1 до p

    for (ll x=1; x<p; x++)

    {

        // Если х является решением, то считать все

        // числа вида x + i * p такие

        // что x + i * p находится в диапазоне [1, n]

        if ((x*x)%p == 1)

        {

            // Наибольшее число в

            // форма x + p * i в диапазоне

            // [1, n]

            ll last = x + p * (n/p);

            if (last > n)

                last -= p;

  

            // Добавляем количество чисел формы

            // x + p * i. 1 добавляется для самого x.

            ans += ((last-x)/p + 1);

        }

    }

    return ans;

}

  
// Код драйвера

int main()

{

    ll n = 10, p = 5;

    printf("%lld\n", findCountOfSolutions(n, p));

    return 0;

}

Джава

// Java-программа для подсчета
// количество значений, которые
// удовлетворяем x ^ 2 = 1 mod p
// где x лежит в диапазоне [1, n]

import java.io.*;

  

class GFG

{

static int findCountOfSolutions(int n, 

                                int p)

{

    // Инициализировать результат

    int ans = 0;

  

    // Обход всех номеров

    // меньше заданного

    // номер р. Обратите внимание, что

    // мы не пересекаем

    // 1 в n, но 1 в p

    for (int x = 1; x < p; x++)

    {

        // Если х является решением,

        // затем посчитаем все числа

        // вида x + i * p

        // такой, что x + i * p

        // в диапазоне [1, n]

        if ((x * x) % p == 1)

        {

            // Наибольшее число

            // в форме х +

            // p * i в диапазоне [1, n]

            int last = x + p * (n / p);

            if (last > n)

                last -= p;

  

            // Добавить количество чисел

            // в форме x + p * i.

            // 1 добавлено для самого x.

            ans += ((last - x) / p + 1);

        }

    }

    return ans;

}

  
// Код драйвера

public static void main (String[] args) 

{

    int n = 10;

    int p = 5;

    System.out.println(

               findCountOfSolutions(n, p));

}
}

  
// Этот код предоставлен ajit

python3

# Программа для подсчета количества
# значения, которые удовлетворяют x ^ 2 = 1
# mod p, где x лежит в диапазоне [1, n]

  

def findCountOfSolutions(n, p):

      

    # Инициализировать результат

    ans = 0;

  

    # Пройдите все номера меньше

    # чем задано число р. Заметка

    # что мы не пересекаем

    № 1 до п, но 1 до р

    for x in range(1, p):

          

        # Если х является решением, то

        # считать все числа

        # форма x + i * p такая, что

        # x + i * p находится в диапазоне [1, n]

        if ((x * x) % p == 1):

              

            # Самое большое число в

            # форма x + p * i в диапазоне

            # [1, n]

            last = x + p * (n / p);

            if (last > n):

                last -= p;

  

            # Добавить количество чисел

            # форма x + p * i. 1 является

            # добавлено для самого x.

            ans += ((last - x) / p + 1);

    return int(ans);

  
# Код драйвера

n = 10;

p = 5;

print(findCountOfSolutions(n, p));

      
# Этот код предоставлен mits

C #

// C # программа для подсчета
// количество значений, которые
// удовлетворяем x ^ 2 = 1 mod p
// где x лежит в диапазоне [1, n]

using System;

  

class GFG

{

static int findCountOfSolutions(int n, 

                                int p)

{

    // Инициализировать результат

    int ans = 0;

  

    // Обход всех номеров

    // меньше заданного

    // номер р. Обратите внимание, что

    // мы не пересекаем

    // 1 в n, но 1 в p

    for (int x = 1; x < p; x++)

    {

        // Если х является решением,

        // затем посчитаем все числа

        // вида x + i * p

        // такой, что x + i * p

        // в диапазоне [1, n]

        if ((x * x) % p == 1)

        {

            // Наибольшее число

            // в форме х +

            // p * i в диапазоне [1, n]

            int last = x + p * (n / p);

            if (last > n)

                last -= p;

  

            // Добавить количество чисел

            // в форме x + p * i.

            // 1 добавлено для самого x.

            ans += ((last - x) / p + 1);

        }

    }

    return ans;

}

  
// Код драйвера

static public void Main ()

{

    int n = 10;

    int p = 5;

    Console.WriteLine(

            findCountOfSolutions(n, p));

}
}

  
// Этот код предоставлен ajit

PHP

<?php
// Программа для подсчета количества
// значения, которые удовлетворяют x ^ 2 = 1
// mod p, где x лежит в диапазоне [1, n]

  

function findCountOfSolutions($n, $p)

{

    // Инициализировать результат

    $ans = 0;

  

    // Обходим все числа меньше

    // чем задано число р. Заметка

    // что мы не пересекаем

    // 1 в n, но 1 в p

    for ($x = 1; $x < $p; $x++)

    {

        // Если х является решением, то

        // посчитаем все числа

        // формируем x + i * p так, что

        // x + i * p находится в диапазоне [1, n]

        if (($x * $x) % $p == 1)

        {

            // Наибольшее число в

            // форма x + p * i в диапазоне

            // [1, n]

            $last = $x + $p * ($n / $p);

            if ($last > $n)

                $last -= $p;

  

            // Добавить количество чисел

            // форма x + p * i. 1 является

            // добавлено для самого x.

            $ans += (($last - $x) / $p + 1);

        }

    }

    return $ans;

}

  
// Код драйвера

$n = 10;

$p = 5;

echo findCountOfSolutions($n, $p);

      
// Этот код предоставлен ajit
?>


Выход:

4

Эта статья предоставлена Shubham Agrawal . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Подсчитать количество решений x ^ 2 = 1 (mod p) в заданном диапазоне

0.00 (0%) 0 votes