Dado un número N. La tarea es encontrar el número de pares de enteros coprimos no ordenados del 1 al N. Puede haber múltiples consultas.
Ejemplos:
Input: 3 Output: 4 (1, 1), (1, 2), (1, 3), (2, 3) Input: 4 Output: 6 (1, 1), (1, 2), (1, 3), (1, 4), (2, 3), (3, 4)
Enfoque: aquí la función Totient de Euler será útil. La función totient de Euler denotada como phi(N), es una función aritmética que cuenta los números enteros positivos menores o iguales a N que son primos relativos a N.
La idea es usar las siguientes propiedades de la función Euler Totient, es decir
- La fórmula básicamente dice que el valor de Φ(n) es igual a n multiplicado por el producto de (1 – 1/p) para todos los factores primos p de n. Por ejemplo , valor de Φ(6) = 6 * (1-1/2) * (1 – 1/3) = 2.
- Para un número primo p, Φ(p) es p-1. Por ejemplo , Φ(5) es 4, Φ(7) es 6 y Φ(13) es 12. Esto es obvio, el mcd de todos los números del 1 al p-1 será 1 porque p es un número primo.
Ahora, encuentre la suma de todos los phi (x) para todos los i entre 1 y N usando el método de suma de prefijos. Usando esto, uno puede responder en o (1) tiempo.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to find number of unordered
// coprime pairs of integers from 1 to N
#include <bits/stdc++.h>
using namespace std;
#define N 100005
// to store euler's totient function
int phi[N];
// to store required answer
int S[N];
// Computes and prints totient of all numbers
// smaller than or equal to N.
void computeTotient()
{
// Initialise the phi[] with 1
for (int i = 1; i < N; i++)
phi[i] = i;
// Compute other Phi values
for (int p = 2; p < N; p++) {
// If phi[p] is not computed already,
// then number p is prime
if (phi[p] == p) {
// Phi of a prime number p is
// always equal to p-1.
phi[p] = p - 1;
// Update phi values of all
// multiples of p
for (int i = 2 * p; i < N; i += p) {
// Add contribution of p to its
// multiple i by multiplying with
// (1 - 1/p)
phi[i] = (phi[i] / p) * (p - 1);
}
}
}
}
// function to compute number coprime pairs
void CoPrimes()
{
// function call to compute
// euler totient function
computeTotient();
// prefix sum of all euler totient function values
for (int i = 1; i < N; i++)
S[i] = S[i - 1] + phi[i];
}
// Driver code
int main()
{
// function call
CoPrimes();
int q[] = { 3, 4 };
int n = sizeof(q) / sizeof(q[0]);
for (int i = 0; i < n; i++)
cout << "Number of unordered coprime\n"
<< "pairs of integers from 1 to "
<< q[i] << " are " << S[q[i]] << endl;
return 0;
}
C
// C program to find number of unordered
// coprime pairs of integers from 1 to N
#include <stdio.h>
#define N 100005
// to store euler's totient function
int phi[N];
// to store required answer
int S[N];
// Computes and prints totient of all numbers
// smaller than or equal to N.
void computeTotient()
{
// Initialise the phi[] with 1
for (int i = 1; i < N; i++)
phi[i] = i;
// Compute other Phi values
for (int p = 2; p < N; p++) {
// If phi[p] is not computed already,
// then number p is prime
if (phi[p] == p) {
// Phi of a prime number p is
// always equal to p-1.
phi[p] = p - 1;
// Update phi values of all
// multiples of p
for (int i = 2 * p; i < N; i += p) {
// Add contribution of p to its
// multiple i by multiplying with
// (1 - 1/p)
phi[i] = (phi[i] / p) * (p - 1);
}
}
}
}
// function to compute number coprime pairs
void CoPrimes()
{
// function call to compute
// euler totient function
computeTotient();
// prefix sum of all euler totient function values
for (int i = 1; i < N; i++)
S[i] = S[i - 1] + phi[i];
}
// Driver code
int main()
{
// function call
CoPrimes();
int q[] = { 3, 4 };
int n = sizeof(q) / sizeof(q[0]);
for (int i = 0; i < n; i++)
printf("Number of unordered coprime\npairs of integers from 1 to %d are %d\n",q[i],S[q[i]]);
return 0;
}
// This code is contributed by kothavvsaakash.
Java
// Java program to find number of unordered
// coprime pairs of integers from 1 to N
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
static final int N = 100005;
// to store euler's
// totient function
static int[] phi;
// to store required answer
static int[] S ;
// Computes and prints totient
// of all numbers smaller than
// or equal to N.
static void computeTotient()
{
// Initialise the phi[] with 1
for (int i = 1; i < N; i++)
phi[i] = i;
// Compute other Phi values
for (int p = 2; p < N; p++)
{
// If phi[p] is not computed
// already, then number p is prime
if (phi[p] == p)
{
// Phi of a prime number p
// is always equal to p-1.
phi[p] = p - 1;
// Update phi values of
// all multiples of p
for (int i = 2 * p; i < N; i += p)
{
// Add contribution of p to
// its multiple i by multiplying
// with (1 - 1/p)
phi[i] = (phi[i] / p) * (p - 1);
}
}
}
}
// function to compute
// number coprime pairs
static void CoPrimes()
{
// function call to compute
// euler totient function
computeTotient();
// prefix sum of all euler
// totient function values
for (int i = 1; i < N; i++)
S[i] = S[i - 1] + phi[i];
}
// Driver code
public static void main(String args[])
{
phi = new int[N];
S = new int[N];
// function call
CoPrimes();
int q[] = { 3, 4 };
int n = q.length;
for (int i = 0; i < n; i++)
System.out.println("Number of unordered coprime\n" +
"pairs of integers from 1 to " +
q[i] + " are " + S[q[i]] );
}
}
// This code is contributed
// by Subhadeep
Python 3
# Python3 program to find number
# of unordered coprime pairs of
# integers from 1 to N
N = 100005
# to store euler's totient function
phi = [0] * N
# to store required answer
S = [0] * N
# Computes and prints totient of all
# numbers smaller than or equal to N.
def computeTotient():
# Initialise the phi[] with 1
for i in range(1, N):
phi[i] = i
# Compute other Phi values
for p in range(2, N) :
# If phi[p] is not computed already,
# then number p is prime
if (phi[p] == p) :
# Phi of a prime number p
# is always equal to p-1.
phi[p] = p - 1
# Update phi values of all
# multiples of p
for i in range(2 * p, N, p) :
# Add contribution of p to its
# multiple i by multiplying with
# (1 - 1/p)
phi[i] = (phi[i] // p) * (p - 1)
# function to compute number
# coprime pairs
def CoPrimes():
# function call to compute
# euler totient function
computeTotient()
# prefix sum of all euler
# totient function values
for i in range(1, N):
S[i] = S[i - 1] + phi[i]
# Driver code
if __name__ == "__main__":
# function call
CoPrimes()
q = [ 3, 4 ]
n = len(q)
for i in range(n):
print("Number of unordered coprime\n" +
"pairs of integers from 1 to ",
q[i], " are " , S[q[i]])
# This code is contributed
# by ChitraNayal
C#
// C# program to find number
// of unordered coprime pairs
// of integers from 1 to N
using System;
class GFG
{
static int N = 100005;
// to store euler's
// totient function
static int[] phi;
// to store required answer
static int[] S ;
// Computes and prints totient
// of all numbers smaller than
// or equal to N.
static void computeTotient()
{
// Initialise the phi[] with 1
for (int i = 1; i < N; i++)
phi[i] = i;
// Compute other Phi values
for (int p = 2; p < N; p++)
{
// If phi[p] is not computed
// already, then number p is prime
if (phi[p] == p)
{
// Phi of a prime number p
// is always equal to p-1.
phi[p] = p - 1;
// Update phi values of
// all multiples of p
for (int i = 2 * p;
i < N; i += p)
{
// Add contribution of
// p to its multiple i
// by multiplying
// with (1 - 1/p)
phi[i] = (phi[i] / p) * (p - 1);
}
}
}
}
// function to compute
// number coprime pairs
static void CoPrimes()
{
// function call to compute
// euler totient function
computeTotient();
// prefix sum of all euler
// totient function values
for (int i = 1; i < N; i++)
S[i] = S[i - 1] + phi[i];
}
// Driver code
public static void Main()
{
phi = new int[N];
S = new int[N];
// function call
CoPrimes();
int[] q = { 3, 4 };
int n = q.Length;
for (int i = 0; i < n; i++)
Console.WriteLine("Number of unordered coprime\n" +
"pairs of integers from 1 to " +
q[i] + " are " + S[q[i]] );
}
}
// This code is contributed
// by mits
PHP
<?php
// PHP program to find number
// of unordered coprime pairs
// of integers from 1 to N
$N = 100005;
// to store euler's totient function
$phi = array_fill(0, $N, 0);
// to store required answer
$S = array_fill(0, $N, 0);
// Computes and prints totient
// of all numbers smaller than
// or equal to N.
function computeTotient()
{
global $N, $phi, $S;
// Initialise the phi[] with 1
for ($i = 1; $i < $N; $i++)
$phi[$i] = $i;
// Compute other Phi values
for ($p = 2; $p < $N; $p++)
{
// If phi[p] is not computed
// already, then number p
// is prime
if ($phi[$p] == $p)
{
// Phi of a prime number p
// is always equal to p-1.
$phi[$p] = $p - 1;
// Update phi values of
// all multiples of p
for ($i = 2 * $p;
$i < $N; $i += $p)
{
// Add contribution of p
// to its multiple i by
// multiplying with (1 - 1/p)
$phi[$i] = (int)(($phi[$i] /
$p) * ($p - 1));
}
}
}
}
// function to compute
// number coprime pairs
function CoPrimes()
{
global $N, $phi, $S;
// function call to compute
// euler totient function
computeTotient();
// prefix sum of all euler
// totient function values
for ($i = 1; $i < $N; $i++)
$S[$i] = $S[$i - 1] + $phi[$i];
}
// Driver code
// function call
CoPrimes();
$q = array( 3, 4 );
$n = sizeof($q);
for ($i = 0; $i < $n; $i++)
echo "Number of unordered coprime\n" .
"pairs of integers from 1 to " .
$q[$i] . " are ".$S[$q[$i]]."\n";
// This code is contributed
// by mits
?>
Javascript
<script>
// Javascript program to find number of unordered
// coprime pairs of integers from 1 to N
let N = 100005;
// to store euler's
// totient function
let phi = new Array(N);
// to store required answer
let S = new Array(N);
for(let i = 0; i < N; i++)
{
phi[i] = 0;
S[i] = 0;
}
// Computes and prints totient
// of all numbers smaller than
// or equal to N.
function computeTotient()
{
// Initialise the phi[] with 1
for (let i = 1; i < N; i++)
phi[i] = i;
// Compute other Phi values
for (let p = 2; p < N; p++)
{
// If phi[p] is not computed
// already, then number p is prime
if (phi[p] == p)
{
// Phi of a prime number p
// is always equal to p-1.
phi[p] = p - 1;
// Update phi values of
// all multiples of p
for (let i = 2 * p; i < N; i += p)
{
// Add contribution of p to
// its multiple i by multiplying
// with (1 - 1/p)
phi[i] = (phi[i] / p) * (p - 1);
}
}
}
}
// function to compute
// number coprime pairs
function CoPrimes()
{
// function call to compute
// euler totient function
computeTotient();
// prefix sum of all euler
// totient function values
for (let i = 1; i < N; i++)
S[i] = S[i - 1] + phi[i];
}
// Driver code
// function call
CoPrimes();
let q = [ 3, 4 ];
let n = q.length;
for (let i = 0; i < n; i++)
document.write("Number of unordered coprime<br>" +
"pairs of integers from 1 to " +
q[i] + " are " + S[q[i]] +"<br>" );
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Number of unordered coprime pairs of integers from 1 to 3 are 4 Number of unordered coprime pairs of integers from 1 to 4 are 6
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA