Сумма произведения x и y таких, что floor (n / x) = y

Опубликовано: 20 Января, 2022

Дано натуральное число n . Задача состоит в том, чтобы найти такую сумму произведения x и y , что ⌊n / x⌋ = y (целочисленное деление).

Примеры:

 Ввод: n = 5
Выход: 21
Ниже приведены возможные пары (x, y):
(1, 5), (2, 2), (3, 1), (4, 1), (5, 1).
Итак, 1 * 5 + 2 * 2 + 3 * 1 + 4 * 1 + 5 * 1 
   = 5 + 4 + 3 + 4 + 5 
   = 21.

Ввод: n = 10
Выход: 87
Рекомендуется: сначала решите эту проблему на «ПРАКТИКЕ», прежде чем переходить к решению.

Метод 1 (грубая сила):
Итерируйте x от 1 до n, чтобы найти y. Затем добавляйте x * y к ответу на каждой итерации.

Below is the implementation of this approach :  

C++

// C++ program to find sum of product of x and y
// such that n/x = y (Integer Division)
#include<bits/stdc++.h>
using namespace std;
 
// Return the sum of product x*y.
int sumofproduct(int n)
{
    int ans = 0;
 
    // Iterating x from 1 to n
    for (int x = 1; x <= n; x++)
    {
        // Finding y = n/x.
        int y = n/x;
 
        // Adding product of x and y to answer.
        ans += (y * x);
    }
 
    return ans;
}
 
// Driven Program
int main()
{
    int n = 10;
    cout << sumofproduct(n) << endl;
    return 0;
}

Java

// Java program to find sum of
// product of x and y such that
// n/x = y (Integer Division)
import java.io.*;
 
class GFG {
     
// Return the sum of product x*y.
static int sumofproduct(int n)
{
    int ans = 0;
 
    // Iterating x from 1 to n
    for (int x = 1; x <= n; x++)
    {
        // Finding y = n/x.
        int y = n / x;
 
        // Adding product of x and
        // y to answer.
        ans += (y * x);
    }
 
    return ans;
}
 
    // Driver Code
    static public void main(String[] args)
    {
        int n = 10;
        System.out.println(sumofproduct(n));
    }
}
 
// This code is contributed by vt_m.

Python3

# Python3 program to find sum of
# product of x and y such that
# n/x = y (Integer Division)
 
# Return the sum of product x*y
def sumofproduct(n):
    ans = 0
 
    # Iterating x from 1 to n
    for x in range(1, n + 1):
         
        # Finding y = n/x.
        y = int(n / x)
 
        # Adding product of x and y to answer.
        ans += (y * x)
 
    return ans
 
# Driven Program
n = 10
print (sumofproduct(n))
 
#This code is Shreyanshi Arun

C#

// C# program to find sum of
// product of x and y such that
// n/x = y (Integer Division)
using System;
 
class GFG {
     
// Return the sum of product x*y.
static int sumofproduct(int n)
{
    int ans = 0;
 
    // Iterating x from 1 to n
    for (int x = 1; x <= n; x++)
    {
        // Finding y = n/x.
        int y = n / x;
 
        // Adding product of x and
        // y to answer.
        ans += (y * x);
    }
 
    return ans;
}
 
    // Driver Code
    static public void Main(String[] args)
    {
        int n = 10;
        Console.WriteLine(sumofproduct(n));
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP program to find sum of product
// of x and y such that n/x = y
// (Integer Division)
 
// Return the sum of product x*y.
function sumofproduct($n)
{
    $ans = 0;
 
    // Iterating x from 1 to n
    for($x = 1; $x <= $n; $x++)
    {
        // Finding y = n/x.
        $y = (int)($n / $x);
 
        // Adding product of x
        // and y to answer.
        $ans += ($y * $x);
    }
 
    return $ans;
}
 
// Driver Code
$n = 10;
echo sumofproduct($n);
 
// This code is contributed by mits
?>

Javascript

<script>
 
// Javascript program to find sum of
// product of x and y such that
// n/x = y (Integer Division)
    
// Return the sum of product x*y.
function sumofproduct(n)
{
    var ans = 0;
 
    // Iterating x from 1 to n
    for(x = 1; x <= n; x++)
    {
         
        // Finding y = n/x.
        var y = parseInt(n / x);
 
        // Adding product of x and
        // y to answer.
        ans += (y * x);
    }
    return ans;
}
 
// Driver Code
var n = 10;
document.write(sumofproduct(n));
 
// This code is contributed by Princi Singh
 
</script>

Выход :

87

Сложность времени: O (n)
Метод 2 (эффективный подход):
Решим для n = 10, поэтому
х = 1, у = 10
х = 2, у = 5
х = 3, у = 3
х = 4, у = 2
х = 5, у = 2
х = 6, у = 1
х = 7, у = 1
х = 8, у = 1
х = 9, у = 1
х = 10, у = 1
Итак, наш ответ будет 1 * 10 + 2 * 5 + 3 * 3 + 4 * 2 + 5 * 2 + 6 * 1 + 7 * 1 + 8 * 1 + 9 * 1 + 10 * 1.
Теперь обратите внимание, что некоторое значение y повторяется. Также обратите внимание, что они повторяются для некоторого диапазона последовательных значений x, например, y = 1 повторяется для x = от 6 до 10.

Итак, вместо того, чтобы найти значение y для всех значений x (от 1 до n), как это сделано в методе 1, попробуйте найти меньшее и большее значение x, для которого значение возможного значения y, как для y = 1 попробуйте найти меньшее значение x = 6 и большее значение x = 10. Теперь обратите внимание, что меньшее значение будет (n / (y + 1)) + 1, а более высокое значение будет (n / y). Найдите сумму диапазона x, умножьте на y и прибавьте к ответу.
Как найти возможное значение y?

Обратите внимание, y имеет все значения от 1 до sqrt (n), когда y меньше или равно x. Итак, от y = 1 до sqrt (n) найдите нижний и верхний пределы x для каждого y. Для n = 10
y = 1, lo = 6 и hi = 10, ans + = (6 + 7 + 8 + 9 + 10) * 1
y = 2, lo = 4 и hi = 5, ans + = (4 + 5) * 2
y = 3, lo = 3 и hi = 3, ans + = (3) * 3

Для добавления других значений (для y = 10 и 5 в n = 10) обратите внимание, что они могут быть найдены в приведенных выше шагах, для каждого y добавьте y * (n / y) в ответ.
Для n = 10
у = 1, ANS + = 1 * (10/1)
у = 2, ANS + = 2 * (10/2).

Below is the implementation of this approach:  

C++

// C++ program to find sum of product of x and y
// such that n/x = y (Integer Division)
#include<bits/stdc++.h>
using namespace std;
 
// Return the sum of natural number in a range.
int sumOfRange(int a, int b)
{
    // n*(n+1)/2.
    int i = (a * (a+1)) >> 1;
    int j = (b * (b+1)) >> 1;
    return (i - j);
}
 
// Return the sum of product x*y.
int sumofproduct(int n)
{
    int sum = 0;
 
    // Iterating i from 1 to sqrt(n)
    int root = sqrt(n);
    for (int i=1; i<=root; i++)
    {
        // Finding the upper limit.
        int up = n/i;
 
        // Finding the lower limit.
        int low = max(n/(i+1), root);
 
        sum += (i * sumOfRange(up, low));
        sum += (i * (n/i));
    }
 
    return sum;
}
 
// Driven Program
int main()
{
    int n = 10;
    cout << sumofproduct(n) << endl;
    return 0;
}

Java

// Java program to find sum of
// product of x and y such that
// n / x = y (Integer Division)
import java.io.*;
 
class GFG {
     
// Return the sum of natural number in a range.
static int sumOfRange(int a, int b)
{
    // n * (n + 1) / 2.
    int i = (a * (a + 1)) >> 1;
    int j = (b * (b + 1)) >> 1;
    return (i - j);
}
 
// Return the sum of product x*y.
static int sumofproduct(int n)
{
    int sum = 0;
 
    // Iterating i from 1 to sqrt(n)
    int root = (int)Math.sqrt(n);
    for (int i = 1; i <= root; i++)
    {
        // Finding the upper limit.
        int up = n / i;
 
        // Finding the lower limit.
        int low = Math.max(n / (i + 1), root);
 
        sum += (i * sumOfRange(up, low));
        sum += (i * (n / i));
    }
 
    return sum;
}
 
    // Driver Code
    static public void main(String[] args)
    {
        int n = 10;
        System.out.println(sumofproduct(n));
    }
}
 
// This code is contributed by vt_m.

Python3

# Python3 program to find sum
# of product of x and y such
# that n/x = y (Integer Division)
import math
 
# Return the sum of natural
# number in a range.
def sumOfRange(a, b):
    # n*(n+1)/2.
    i = (a * (a + 1)) >> 1;
    j = (b * (b + 1)) >> 1;
    return (i - j);
 
# Return the sum of product x*y.
def sumofproduct(n):
    sum = 0;
 
    # Iterating i from 1 to sqrt(n)
    root = int(math.sqrt(n));
    for i in range(1, root + 1):
        # Finding the upper limit.
        up = int(n / i);
 
        # Finding the lower limit.
        low = max(int(n / (i + 1)), root);
 
        sum += (i * sumOfRange(up, low));
        sum += (i * int(n / i));
 
    return sum;
 
# Driven Code
n = 10;
print(sumofproduct(n));
     
# This code is contributed by mits

C#

// C# program to find sum of
// product of x and y such that
// n / x = y (Integer Division)
using System;
 
class GFG {
     
// Return the sum of natural number in a range.
static int sumOfRange(int a, int b)
{
    // n * (n + 1) / 2.
    int i = (a * (a + 1)) >> 1;
    int j = (b * (b + 1)) >> 1;
    return (i - j);
}
 
// Return the sum of product x*y.
static int sumofproduct(int n)
{
    int sum = 0;
 
    // Iterating i from 1 to sqrt(n)
    int root = (int)Math.Sqrt(n);
    for (int i = 1; i <= root; i++)
    {
        // Finding the upper limit.
        int up = n / i;
 
        // Finding the lower limit.
        int low = Math.Max(n / (i + 1), root);
 
        sum += (i * sumOfRange(up, low));
        sum += (i * (n / i));
    }
 
    return sum;
}
 
    // Driver Code
    static public void Main(String[] args)
    {
        int n = 10;
        Console.WriteLine(sumofproduct(n));
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP program to find sum of
// product of x and y such
// that n/x = y (Integer Division)
 
// Return the sum of natural
// number in a range.
function sumOfRange($a, $b)
{
    // n*(n+1)/2.
    $i = ($a * ($a + 1)) >> 1;
    $j = ($b * ($b + 1)) >> 1;
    return ($i - $j);
}
 
// Return the sum of product x*y.
function sumofproduct($n)
{
    $sum = 0;
 
    // Iterating i from 1 to sqrt(n)
    $root = sqrt($n);
    for ($i = 1; $i <= $root; $i++)
    {
        // Finding the upper limit.
        $up = (int)($n / $i);
 
        // Finding the lower limit.
        $low = max((int)($n / ($i + 1)), $root);
 
        $sum += ($i * sumOfRange($up, $low));
        $sum += ($i * (int)($n / $i));
    }
 
    return $sum;
}
 
// Driven Code
$n = 10;
echo sumofproduct($n) . " ";
 
// This code is contributed
// by Akanksha Rai(Abby_akku)
?>

Javascript

<script>
 
// Javascript program to implement
// the above approach
 
// Return the sum of natural number in a range.
function sumOfRange(a, b)
{
    // n * (n + 1) / 2.
    let i = (a * (a + 1)) >> 1;
    let j = (b * (b + 1)) >> 1;
    return (i - j);
}
  
// Return the sum of product x*y.
function sumofproduct(n)
{
    let sum = 0;
  
    // Iterating i from 1 to sqrt(n)

РЕКОМЕНДУЕМЫЕ СТАТЬИ