Рубрики

Подсчитать пары натуральных чисел с GCD, равным данному числу

Даны три положительных целых числа L , R , G. Задача состоит в том, чтобы найти число пар (x, y), имеющих GCD (x, y) = G и x, y лежат между L и R.

Примеры:

Input : L = 1, R = 11, G = 5
Output : 3
(5, 5), (5, 10), (10, 5) are three pair having GCD equal to 5 and lie between 1 and 11.
So answer is 3.

Input : L = 1, R = 10, G = 7
Output : 1

Простое решение — пройти через все пары в [L, R]. Для каждой пары найдите свой GCD. Если GCD равен g, то счетчик приращений. Наконец вернуть счет.

Эффективное решение основано на том факте, что для любой положительной целой пары (x, y) GCD, равной g, x и y, должна делиться на g.
Заметим, что между L и R будет не более (R — L) / g чисел, которые делятся на g.
Таким образом, мы находим числа между L и R, которые делятся на g. Для этого мы начнем с ceil (L / g) * g и с шагом приращения g на каждом шаге, пока он не превышает R, число чисел с GCD равно 1.
Также,

ceil(L/g) * g = floor((L + g - 1) / g) * g.

Ниже приведена реализация вышеуказанной идеи:

C ++

// C ++ программа для подсчета пары в диапазоне натуральных
// число, имеющее GCD, равное данному числу.
#include <bits/stdc++.h>

using namespace std;

  
// Возвращаем GCD из двух чисел.

int gcd(int a, int b)

{

    return b ? gcd(b, a % b) : a;

}

  
// Возвращаем количество пар, имеющих GCD, равный g.

int countGCD(int L, int R, int g)

{

    // Установка значения L, R.

    L = (L + g - 1) / g;

    R = R/ g;

  

    // Для каждой возможной пары проверяем, равен ли GCD 1.

    int ans = 0;

    for (int i = L; i <= R; i++)

        for (int j = L; j <= R; j++)

            if (gcd(i, j) == 1)

                ans++;

  

    return ans;

}

  
// Управляемая программа

int main()

{

    int L = 1, R = 11, g = 5;

    cout << countGCD(L, R, g) << endl;

    return 0;

}

Джава

// Java-программа для подсчета пары
// диапазон натурального числа, имеющий
// GCD равен заданному номеру.

import java.util.*;

  

class GFG {

      
// Возвращаем GCD из двух чисел.

static int gcd(int a, int b) 

{

    return b > 0 ? gcd(b, a % b) : a; 

}

  
// Возвращаем количество пар
// имеющий GCD, равный g.

static int countGCD(int L, int R, int g) {

      

    // Установка значения L, R.

    L = (L + g - 1) / g;

    R = R / g;

  

    // Для каждой возможной пары проверяем, равен ли GCD 1.

    int ans = 0;

    for (int i = L; i <= R; i++)

    for (int j = L; j <= R; j++)

        if (gcd(i, j) == 1)

        ans++;

  

    return ans;

}

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

public static void main(String[] args) {

      

    int L = 1, R = 11, g = 5;

    System.out.println(countGCD(L, R, g));

}
}

  
// Этот код предоставлен Anant Agarwal.

python3

# Программа Python для подсчета
# пара в диапазоне натуральных
число с GCD равным
# на указанный номер.

  
# Вернуть GCD двух чисел.

def gcd(a,b):

  

    return gcd(b, a % b) if b>0 else a

  

   
# Вернуть количество пар
# с GCD, равным g.

def countGCD(L,R,g):

  

    # Установка значения L, R.

    L = (L + g - 1) // g

    R = R// g

   

    # Для каждой возможной пары

    # проверить, равен ли GCD 1.

    ans = 0

    for i in range(L,R+1):

        for j in range(L,R+1):

            if (gcd(i, j) == 1):

                ans=ans +1

   

    return ans

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

  

L = 1

R = 11

g = 5

  

print(countGCD(L, R, g))

  
# Этот код добавлен
# Анант Агарвал.

C #

// C # программа для подсчета пары
// диапазон натурального числа, имеющий
// GCD равен заданному номеру.

using System;

  

class GFG {

      
// Возвращаем GCD из двух чисел.

static int gcd(int a, int b) 

{

    return b > 0 ? gcd(b, a % b) : a; 

}

  
// Возвращаем количество пар
// имеющий GCD, равный g.

static int countGCD(int L, int R,

                    int g)

{

      

    // Установка значения L, R.

    L = (L + g - 1) / g;

    R = R / g;

  

    // Для каждой возможной пары

    // проверяем, равен ли GCD 1.

    int ans = 0;

    for (int i = L; i <= R; i++)

    for (int j = L; j <= R; j++)

        if (gcd(i, j) == 1)

        ans++;

  

    return ans;

}

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

public static void Main() 

{

      

    int L = 1, R = 11, g = 5;

    Console.WriteLine(countGCD(L, R, g));

}
}

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

PHP

<?php
// PHP программа для подсчета пары
// в диапазоне натурального числа
// имеющий GCD равный данному числу.

  
// Возвращаем GCD из двух чисел.

function gcd( $a, $b)

{

    return $b ? gcd($b, $a % $b) : $a;

}

  
// Возвращаем количество пар
// имеющий GCD, равный g.

function countGCD( $L, $R, $g)

{

      

    // Установка значения L, R.

    $L = ($L + $g - 1) / $g;

    $R = $R/ $g;

  

    // Для каждой возможной пары

    // проверяем, равен ли GCD 1.

    $ans = 0;

    for($i = $L; $i <= $R; $i++)

        for($j = $L; $j <= $R; $j++)

            if (gcd($i, $j) == 1)

                $ans++;

  

    return $ans;

}

  

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

    $L = 1; 

    $R = 11;

    $g = 5;

    echo countGCD($L, $R, $g);

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


Выход:

3

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

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

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

Подсчитать пары натуральных чисел с GCD, равным данному числу

0.00 (0%) 0 votes