Рекомендуется: сначала решите эту проблему на «ПРАКТИКЕ», прежде чем переходить к решению.
Метод 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>
usingnamespacestd;
// Return the sum of product x*y.
intsumofproduct(intn)
{
intans = 0;
// Iterating x from 1 to n
for(intx = 1; x <= n; x++)
{
// Finding y = n/x.
inty = n/x;
// Adding product of x and y to answer.
ans += (y * x);
}
returnans;
}
// Driven Program
intmain()
{
intn = 10;
cout << sumofproduct(n) << endl;
return0;
}
Java
// Java program to find sum of
// product of x and y such that
// n/x = y (Integer Division)
importjava.io.*;
classGFG {
// Return the sum of product x*y.
staticintsumofproduct(intn)
{
intans = 0;
// Iterating x from 1 to n
for(intx = 1; x <= n; x++)
{
// Finding y = n/x.
inty = n / x;
// Adding product of x and
// y to answer.
ans += (y * x);
}
returnans;
}
// Driver Code
staticpublicvoidmain(String[] args)
{
intn = 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
defsumofproduct(n):
ans =0
# Iterating x from 1 to n
forx inrange(1, n +1):
# Finding y = n/x.
y =int(n /x)
# Adding product of x and y to answer.
ans +=(y *x)
returnans
# 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)
usingSystem;
classGFG {
// Return the sum of product x*y.
staticintsumofproduct(intn)
{
intans = 0;
// Iterating x from 1 to n
for(intx = 1; x <= n; x++)
{
// Finding y = n/x.
inty = n / x;
// Adding product of x and
// y to answer.
ans += (y * x);
}
returnans;
}
// Driver Code
staticpublicvoidMain(String[] args)
{
intn = 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.
functionsumofproduct($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;
echosumofproduct($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.
functionsumofproduct(n)
{
varans = 0;
// Iterating x from 1 to n
for(x = 1; x <= n; x++)
{
// Finding y = n/x.
vary = parseInt(n / x);
// Adding product of x and
// y to answer.
ans += (y * x);
}
returnans;
}
// Driver Code
varn = 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).