Dados dos números N y K . Se puede crear una secuencia A 1 , A 2 , ….AN de longitud N colocando números del 1 al K en cada posición, haciendo un total de K N secuencias . La tarea es encontrar la suma de GCD de todas las secuencias formadas. Nota: La respuesta puede ser muy grande, así que tome un módulo de 10 9 + 7 .
Ejemplos:
Entrada: N = 3, K = 2
Salida: 9
Explicación:
El mcd de todas las subsecuencias son:
mcd(1, 1, 1) = 1
mcd(1, 1, 2) = 1
mcd(1, 2, 1) = 1
mcd(1, 2, 2) = 1
mcd(2, 1, 1) = 1
mcd(2, 1, 2) = 1
mcd(2, 2, 1) = 1
mcd(2, 2, 2) = 2
La suma de MCD es 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 = 9.Entrada: N = 3, K = 200
Salida: 10813692
Enfoque ingenuo: la idea es generar todas las subsecuencias posibles de longitud N recursivamente. La suma de GCD de todas las secuencias formadas es el resultado requerido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
// A recursive function that generates all
// the sequence and find GCD
int calculate(int pos, int g, int n, int k)
{
// If we reach the sequence of length N
// g is the GCD of the sequence
if (pos == n) {
return g;
}
// Initialise answer to 0
int answer = 0;
// Placing all possible values at this
// position and recursively find the
// GCD of the sequence
for (int i = 1; i <= k; i++) {
// Take GCD of GCD calculated uptill
// now i.e. g with current element
answer = (answer % MOD
+ calculate(pos + 1, __gcd(g, i), n, k) % MOD);
// Take modulo to avoid overflow
answer %= MOD;
}
// Return the final answer
return answer;
}
// Function that finds the sum of GCD
// of all the subsequence of N length
int sumofGCD(int n, int k)
{
// Recursive function that generates
// the sequence and return the GCD
return calculate(0, 0, n, k);
}
// Driver Code
int main()
{
int N = 3, K = 2;
// Function Call
cout << sumofGCD(N, K);
return 0;
}
Java
// Java implementation of the above approach
class GFG{
static int MOD = (int)1e9 + 7;
// A recursive function that generates all
// the sequence and find GCD
static int calculate(int pos, int g, int n, int k)
{
// If we reach the sequence of length N
// g is the GCD of the sequence
if (pos == n) {
return g;
}
// Initialise answer to 0
int answer = 0;
// Placing all possible values at this
// position and recursively find the
// GCD of the sequence
for (int i = 1; i <= k; i++) {
// Take GCD of GCD calculated uptill
// now i.e. g with current element
answer = (answer % MOD
+ calculate(pos + 1, __gcd(g, i), n, k) % MOD);
// Take modulo to astatic void overflow
answer %= MOD;
}
// Return the final answer
return answer;
}
// Function that finds the sum of GCD
// of all the subsequence of N length
static int sumofGCD(int n, int k)
{
// Recursive function that generates
// the sequence and return the GCD
return calculate(0, 0, n, k);
}
static int __gcd(int a, int b)
{
return b == 0? a:__gcd(b, a % b);
}
// Driver Code
public static void main(String[] args)
{
int N = 3, K = 2;
// Function Call
System.out.print(sumofGCD(N, K));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the # above approach MOD = 1e9 + 7 def gcd(a, b): if (b == 0): return a else: return gcd(b, a % b) # A recursive function that generates all # the sequence and find GCD def calculate(pos, g, n, k): # If we reach the sequence of length N # g is the GCD of the sequence if (pos == n): return g # Initialise answer to 0 answer = 0 # Placing all possible values at this # position and recursively find the # GCD of the sequence for i in range(1, k + 1): # Take GCD of GCD calculated uptill # now i.e. g with current element answer = (answer % MOD + calculate(pos + 1, gcd(g, i), n, k) % MOD) # Take modulo to avoid overflow answer %= MOD # Return the final answer return answer # Function that finds the sum of GCD # of all the subsequence of N length def sumofGCD(n, k): # Recursive function that generates # the sequence and return the GCD return calculate(0, 0, n, k) # Driver code if __name__=="__main__": N = 3 K = 2 # Function Call print(sumofGCD(N, K)) # This code is contributed by rutvik_56
C#
// C# implementation of the above approach
using System;
public class GFG{
static int MOD = (int)1e9 + 7;
// A recursive function that generates all
// the sequence and find GCD
static int calculate(int pos, int g, int n, int k)
{
// If we reach the sequence of length N
// g is the GCD of the sequence
if (pos == n) {
return g;
}
// Initialise answer to 0
int answer = 0;
// Placing all possible values at this
// position and recursively find the
// GCD of the sequence
for (int i = 1; i <= k; i++) {
// Take GCD of GCD calculated uptill
// now i.e. g with current element
answer = (answer % MOD
+ calculate(pos + 1, __gcd(g, i), n, k) % MOD);
// Take modulo to astatic void overflow
answer %= MOD;
}
// Return the readonly answer
return answer;
}
// Function that finds the sum of GCD
// of all the subsequence of N length
static int sumofGCD(int n, int k)
{
// Recursive function that generates
// the sequence and return the GCD
return calculate(0, 0, n, k);
}
static int __gcd(int a, int b)
{
return b == 0 ? a : __gcd(b, a % b);
}
// Driver code
public static void Main(String[] args)
{
int N = 3, K = 2;
// Function call
Console.Write(sumofGCD(N, K));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the above approach
var MOD = 1000000007;
// A recursive function that generates all
// the sequence and find GCD
function calculate(pos, g, n, k)
{
// If we reach the sequence of length N
// g is the GCD of the sequence
if (pos == n) {
return g;
}
// Initialise answer to 0
var answer = 0;
// Placing all possible values at this
// position and recursively find the
// GCD of the sequence
for (var i = 1; i <= k; i++) {
// Take GCD of GCD calculated uptill
// now i.e. g with current element
answer = (answer % MOD
+ calculate(pos + 1, __gcd(g, i), n, k) % MOD);
// Take modulo to avoid overflow
answer %= MOD;
}
// Return the final answer
return answer;
}
function __gcd(a, b)
{
return b == 0? a:__gcd(b, a % b);
}
// Function that finds the sum of GCD
// of all the subsequence of N length
function sumofGCD(n, k)
{
// Recursive function that generates
// the sequence and return the GCD
return calculate(0, 0, n, k);
}
// Driver Code
var N = 3, K = 2;
// Function Call
document.write( sumofGCD(N, K));
</script>
Producción:
9
Complejidad de tiempo: O(N K )
Espacio Auxiliar: O(k * log N)
Enfoque eficiente:
- Dado que los números de la secuencia pueden ser de 1 a K , el valor mcd de la secuencia estará en el rango de 1 a K.
- Sea count[i] el número de secuencias con mcd = i. Para i = 1, no tenemos restricciones sobre qué elementos pueden pertenecer a la secuencia, por lo que en cada uno de los N lugares, tenemos K posibilidades de colocar elementos haciendo que las secuencias totales sean K N . Pero las secuencias resultantes pueden tener un GCD más alto, así que reste los valores contados en exceso:
count[1] = KN - count[2] - count[3] - count[4] - .... count[K]
- De manera similar, para i = 2, dado que todo número debe ser un múltiplo de 2, tenemos K/2 posibilidades en cada lugar, haciendo que el total sea (K/2) N . Y reste todos los valores contados en exceso restando el conteo de secuencia con el GCD de todos los múltiplos de 2.
count[2] = (K/2)N - count[4] - count[6] - count[8] - ... all multiples of 2
- De manera similar, siga los pasos anteriores para cada valor de gcd a K.
- La suma de cada valor de GCD (digamos g ) con cuenta [g] es la suma de GCD de todas las secuencias formadas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
// Function to find a^b in log(b)
int fastexpo(int a, int b)
{
int res = 1;
a %= MOD;
while (b) {
if (b & 1)
res = (res * a) % MOD;
a *= a;
a %= MOD;
b >>= 1;
}
return res;
}
// Function that finds the sum of GCD
// of all the subsequence of N length
int sumofGCD(int n, int k)
{
// To stores the number of sequences
// with gcd i
int count[k + 1] = { 0 };
// Find contribution of each gcd
// to happen
for (int g = k; g >= 1; g--) {
// To count multiples
int count_multiples = k / g;
// possible sequences with
// overcounting
int temp;
temp = fastexpo(count_multiples, n);
// to avoid overflow
temp %= MOD;
// Find extra element which will
// not form gcd = i
int extra = 0;
// Find overcounting
for (int j = g * 2; j <= k; j += g) {
extra = (extra + count[j]);
extra %= MOD;
}
// Remove the overcounting
count[g] = (temp - extra + MOD);
count[g] %= MOD;
}
// To store the final answer
int sum = 0;
int add;
for (int i = 1; i <= k; ++i) {
add = (count[i] % MOD * i % MOD);
add %= MOD;
sum += add;
sum %= MOD;
}
// Return Final answer
return sum;
}
// Driver Code
int main()
{
int N = 3, K = 2;
// Function call
cout << sumofGCD(N, K);
return 0;
}
Java
// Java implementation of the above approach
class GFG{
static int MOD = (int)1e9 + 7;
// Function to find a^b in log(b)
static int fastexpo(int a, int b)
{
int res = 1;
a %= MOD;
while (b > 0) {
if (b % 2 == 1)
res = (res * a) % MOD;
a *= a;
a %= MOD;
b >>= 1;
}
return res;
}
// Function that finds the sum of GCD
// of all the subsequence of N length
static int sumofGCD(int n, int k)
{
// To stores the number of sequences
// with gcd i
int []count = new int[k + 1];
// Find contribution of each gcd
// to happen
for (int g = k; g >= 1; g--) {
// To count multiples
int count_multiples = k / g;
// possible sequences with
// overcounting
int temp;
temp = fastexpo(count_multiples, n);
// to astatic void overflow
temp %= MOD;
// Find extra element which will
// not form gcd = i
int extra = 0;
// Find overcounting
for (int j = g * 2; j <= k; j += g) {
extra = (extra + count[j]);
extra %= MOD;
}
// Remove the overcounting
count[g] = (temp - extra + MOD);
count[g] %= MOD;
}
// To store the final answer
int sum = 0;
int add;
for (int i = 1; i <= k; ++i) {
add = (count[i] % MOD * i % MOD);
add %= MOD;
sum += add;
sum %= MOD;
}
// Return Final answer
return sum;
}
// Driver Code
public static void main(String[] args)
{
int N = 3, K = 2;
// Function call
System.out.print(sumofGCD(N, K));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation of the above approach MOD = (int)(1e9 + 7) # Function to find a^b in log(b) def fastexpo(a, b) : res = 1 a = a % MOD while (b > 0) : if ((b & 1) != 0) : res = (res * a) % MOD a = a * a a = a % MOD b = b >> 1 return res # Function that finds the sum of GCD # of all the subsequence of N length def sumofGCD(n, k) : # To stores the number of sequences # with gcd i count = [0] * (k + 1) # Find contribution of each gcd # to happen for g in range(k, 0, -1) : # To count multiples count_multiples = k // g # possible sequences with # overcounting temp = fastexpo(count_multiples, n) # to avoid overflow temp = temp % MOD # Find extra element which will # not form gcd = i extra = 0 # Find overcounting for j in range(g * 2, k + 1, g) : extra = extra + count[j] extra = extra % MOD # Remove the overcounting count[g] = temp - extra + MOD count[g] = count[g] % MOD # To store the final answer Sum = 0 for i in range(1, k + 1) : add = count[i] % MOD * i % MOD add = add % MOD Sum = Sum + add Sum = Sum % MOD # Return Final answer return Sum # Driver code N, K = 3, 2 # Function call print(sumofGCD(N, K)) # This code is contributed by divyeshrabadiya07.
C#
// C# implementation of the above approach
using System;
class GFG{
static int MOD = (int)1e9 + 7;
// Function to find a^b in log(b)
static int fastexpo(int a, int b)
{
int res = 1;
a %= MOD;
while (b > 0) {
if (b % 2 == 1)
res = (res * a) % MOD;
a *= a;
a %= MOD;
b >>= 1;
}
return res;
}
// Function that finds the sum of GCD
// of all the subsequence of N length
static int sumofGCD(int n, int k)
{
// To stores the number of sequences
// with gcd i
int []count = new int[k + 1];
// Find contribution of each gcd
// to happen
for (int g = k; g >= 1; g--) {
// To count multiples
int count_multiples = k / g;
// possible sequences with
// overcounting
int temp;
temp = fastexpo(count_multiples, n);
// to astatic void overflow
temp %= MOD;
// Find extra element which will
// not form gcd = i
int extra = 0;
// Find overcounting
for (int j = g * 2; j <= k; j += g) {
extra = (extra + count[j]);
extra %= MOD;
}
// Remove the overcounting
count[g] = (temp - extra + MOD);
count[g] %= MOD;
}
// To store the readonly answer
int sum = 0;
int add;
for (int i = 1; i <= k; ++i) {
add = (count[i] % MOD * i % MOD);
add %= MOD;
sum += add;
sum %= MOD;
}
// Return Final answer
return sum;
}
// Driver Code
public static void Main(String[] args)
{
int N = 3, K = 2;
// Function call
Console.Write(sumofGCD(N, K));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript implementation of the above approach
var MOD = 1000000007;
// Function to find a^b in log(b)
function fastexpo(a, b)
{
var res = 1;
a %= MOD;
while (b) {
if (b & 1)
res = (res * a) % MOD;
a *= a;
a %= MOD;
b >>= 1;
}
return res;
}
// Function that finds the sum of GCD
// of all the subsequence of N length
function sumofGCD( n, k)
{
// To stores the number of sequences
// with gcd i
var count = Array(k+1).fill(0);
// Find contribution of each gcd
// to happen
for (var g = k; g >= 1; g--) {
// To count multiples
var count_multiples = k / g;
// possible sequences with
// overcounting
var temp;
temp = fastexpo(count_multiples, n);
// to avoid overflow
temp %= MOD;
// Find extra element which will
// not form gcd = i
var extra = 0;
// Find overcounting
for (var j = g * 2; j <= k; j += g) {
extra = (extra + count[j]);
extra %= MOD;
}
// Remove the overcounting
count[g] = (temp - extra + MOD);
count[g] %= MOD;
}
// To store the final answer
var sum = 0;
var add;
for (var i = 1; i <= k; ++i) {
add = (count[i] % MOD * i % MOD);
add %= MOD;
sum += add;
sum %= MOD;
}
// Return Final answer
return sum;
}
// Driver Code
var N = 3, K = 2;
// Function call
document.write( sumofGCD(N, K));
</script>
Producción:
9
Complejidad de tiempo: O( K*log(N) + K*log(log(K)) )
Espacio auxiliar: O(K)