Dados dos enteros N y K , la tarea es encontrar el conteo de cuádruples de (i, j, k, l) tales que 1 ≤ i < j < k < l ≤ N y mcd(i, j, k, l) = K.
Ejemplos:
Entrada: N = 10, K = 2
Salida: 5
Los cuádruples válidos son (2, 4, 6, 8), (2, 4, 6, 10),
(2, 4, 8, 10), (2, 6, 8, 10) y (4, 6, 8, 10)
Entrada: N = 8, K = 1
Salida: 69
Acercarse:
- Si el mcd de una secuencia es K , entonces cuando dividimos todos estos números por K , el mcd de los números sobrantes será 1 .
- Ahora, para cumplir con esta restricción de cuádruples que tienen un número máximo N , si encontramos el recuento de todos los cuádruples que tienen un número máximo menor o igual a N / K y tienen mcd 1 , entonces simplemente podemos multiplicar todos los cuádruples con K para obtener la respuesta.
- Para encontrar cuádruples cuentan con mcd 1 , debemos usar el principio de inclusión y exclusión. Tome N / K = M .
- M C 4 cuádruples son posibles en total. (M/2) C 4 cuádruples tienen mcd que es múltiplo de 2 . (Se utilizan M/2 múltiplos de 2). De manera similar, (M/3) C 4 cuádruples tienen mcd que es un múltiplo de 3 . Pero si restamos ambas cantidades entonces, gcd que son múltiplos de 6 se restan dos veces, por lo que debemos incluir (M/6) C 4 para sumarlas una vez.
- Por lo tanto, iterar de 2 a M , y si un número tiene un número impar de divisores primos distintos (como 2, 3, 5, 11), reste el conteo de cuádruples con gcd múltiplo de ese número, y si tiene un número par de primos distintos divisores (como 6, 10, 33) luego sume la cuenta de cuádruples con mcd múltiplo de ese número. (El número no debe tener una repetición de divisores primos como 4).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate NC4
int nCr(int n)
{
// Base case to calculate NC4
if (n < 4)
return 0;
int answer = n * (n - 1) * (n - 2) * (n - 3);
answer /= 24;
return answer;
}
// Function to return the count of required
// quadruples using Inclusion Exclusion
int countQuadruples(int N, int K)
{
// Effective N
int M = N / K;
int answer = nCr(M);
// Iterate over 2 to M
for (int i = 2; i < M; i++) {
int j = i;
// Number of divisors of i till M
int temp2 = M / i;
// Count stores the number of prime
// divisors occurring exactly once
int count = 0;
// To prevent repetition of prime divisors
int check = 0;
int temp = j;
while (j % 2 == 0) {
count++;
j /= 2;
if (count >= 2)
break;
}
if (count >= 2) {
check = 1;
}
for (int k = 3; k <= sqrt(temp); k += 2) {
int cnt = 0;
while (j % k == 0) {
cnt++;
j /= k;
if (cnt >= 2)
break;
}
if (cnt >= 2) {
check = 1;
break;
}
else if (cnt == 1)
count++;
}
if (j > 2) {
count++;
}
// If repetition of prime divisors present
// ignore this number
if (check)
continue;
else {
// If prime divisor count is odd
// subtract it from answer else add
if (count % 2 == 1) {
answer -= nCr(temp2);
}
else {
answer += nCr(temp2);
}
}
}
return answer;
}
// Driver code
int main()
{
int N = 10, K = 2;
cout << countQuadruples(N, K);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to calculate NC4
static int nCr(int n)
{
// Base case to calculate NC4
if (n < 4)
return 0;
int answer = n * (n - 1) * (n - 2) * (n - 3);
answer /= 24;
return answer;
}
// Function to return the count of required
// quadruples using Inclusion Exclusion
static int countQuadruples(int N, int K)
{
// Effective N
int M = N / K;
int answer = nCr(M);
// Iterate over 2 to M
for (int i = 2; i < M; i++)
{
int j = i;
// Number of divisors of i till M
int temp2 = M / i;
// Count stores the number of prime
// divisors occurring exactly once
int count = 0;
// To prevent repetition of prime divisors
int check = 0;
int temp = j;
while (j % 2 == 0)
{
count++;
j /= 2;
if (count >= 2)
break;
}
if (count >= 2)
{
check = 1;
}
for (int k = 3; k <= Math.sqrt(temp); k += 2)
{
int cnt = 0;
while (j % k == 0)
{
cnt++;
j /= k;
if (cnt >= 2)
break;
}
if (cnt >= 2)
{
check = 1;
break;
}
else if (cnt == 1)
count++;
}
if (j > 2)
{
count++;
}
// If repetition of prime divisors present
// ignore this number
if (check==1)
continue;
else
{
// If prime divisor count is odd
// subtract it from answer else add
if (count % 2 == 1)
{
answer -= nCr(temp2);
}
else
{
answer += nCr(temp2);
}
}
}
return answer;
}
// Driver code
public static void main(String[] args)
{
int N = 10, K = 2;
System.out.println(countQuadruples(N, K));
}
}
// This code is contributed by Princi Singh
Python3
# Python3 implementation of the approach from math import sqrt # Function to calculate NC4 def nCr(n) : # Base case to calculate NC4 if (n < 4) : return 0; answer = n * (n - 1) * (n - 2) * (n - 3); answer //= 24; return answer; # Function to return the count of required # quadruples using Inclusion Exclusion def countQuadruples(N, K) : # Effective N M = N // K; answer = nCr(M); # Iterate over 2 to M for i in range(2, M) : j = i; # Number of divisors of i till M temp2 = M // i; # Count stores the number of prime # divisors occurring exactly once count = 0; # To prevent repetition of prime divisors check = 0; temp = j; while (j % 2 == 0) : count += 1; j //= 2; if (count >= 2) : break; if (count >= 2) : check = 1; for k in range(3, int(sqrt(temp)), 2) : cnt = 0; while (j % k == 0) : cnt += 1; j //= k; if (cnt >= 2) : break; if (cnt >= 2) : check = 1; break; elif (cnt == 1) : count += 1; if (j > 2) : count += 1; # If repetition of prime divisors present # ignore this number if (check) : continue; else : # If prime divisor count is odd # subtract it from answer else add if (count % 2 == 1) : answer -= nCr(temp2); else : answer += nCr(temp2); return answer; # Driver code if __name__ == "__main__" : N = 10; K = 2; print(countQuadruples(N, K)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to calculate NC4
static int nCr(int n)
{
// Base case to calculate NC4
if (n < 4)
return 0;
int answer = n * (n - 1) * (n - 2) * (n - 3);
answer /= 24;
return answer;
}
// Function to return the count of required
// quadruples using Inclusion Exclusion
static int countQuadruples(int N, int K)
{
// Effective N
int M = N / K;
int answer = nCr(M);
// Iterate over 2 to M
for (int i = 2; i < M; i++)
{
int j = i;
// Number of divisors of i till M
int temp2 = M / i;
// Count stores the number of prime
// divisors occurring exactly once
int count = 0;
// To prevent repetition of prime divisors
int check = 0;
int temp = j;
while (j % 2 == 0)
{
count++;
j /= 2;
if (count >= 2)
break;
}
if (count >= 2)
{
check = 1;
}
for (int k = 3; k <= Math.Sqrt(temp); k += 2)
{
int cnt = 0;
while (j % k == 0)
{
cnt++;
j /= k;
if (cnt >= 2)
break;
}
if (cnt >= 2)
{
check = 1;
break;
}
else if (cnt == 1)
count++;
}
if (j > 2)
{
count++;
}
// If repetition of prime divisors present
// ignore this number
if (check==1)
continue;
else
{
// If prime divisor count is odd
// subtract it from answer else add
if (count % 2 == 1)
{
answer -= nCr(temp2);
}
else
{
answer += nCr(temp2);
}
}
}
return answer;
}
// Driver code
public static void Main(String[] args)
{
int N = 10, K = 2;
Console.WriteLine(countQuadruples(N, K));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
// Function to calculate NC4
function nCr(n)
{
// Base case to calculate NC4
if (n < 4)
return 0;
let answer = n * (n - 1) * (n - 2) * (n - 3);
answer = parseInt(answer / 24);
return answer;
}
// Function to return the count of required
// quadruples using Inclusion Exclusion
function countQuadruples(N, K)
{
// Effective N
let M = parseInt(N / K);
let answer = nCr(M);
// Iterate over 2 to M
for (let i = 2; i < M; i++) {
let j = i;
// Number of divisors of i till M
let temp2 = parseInt(M / i);
// Count stores the number of prime
// divisors occurring exactly once
let count = 0;
// To prevent repetition of prime divisors
let check = 0;
let temp = j;
while (j % 2 == 0) {
count++;
j = parseInt(j / 2);
if (count >= 2)
break;
}
if (count >= 2) {
check = 1;
}
for (let k = 3; k <= Math.sqrt(temp); k += 2)
{
let cnt = 0;
while (j % k == 0) {
cnt++;
j = parseInt(j / k);
if (cnt >= 2)
break;
}
if (cnt >= 2) {
check = 1;
break;
}
else if (cnt == 1)
count++;
}
if (j > 2) {
count++;
}
// If repetition of prime divisors present
// ignore this number
if (check)
continue;
else {
// If prime divisor count is odd
// subtract it from answer else add
if (count % 2 == 1) {
answer -= nCr(temp2);
}
else {
answer += nCr(temp2);
}
}
}
return answer;
}
// Driver code
let N = 10, K = 2;
document.write(countQuadruples(N, K));
</script>
Producción:
5
Complejidad de tiempo: O(sqrt(n)*n)
Espacio Auxiliar: O(1)