Sum divides product
Problem credits : Codechef
Section : Hard
Problem Statement :
For a given positive integer N find the number of all pairs (a, b) of positive integers such that 1 <= a < b <= N and the sum a + b divides the product a * b.
The problem is simple and easy to code.
First thing we need to do is to generate all such possible pairs 1 <= a < b <= N.
Don't get confused with the mathematical expression, in coding or algorithm I will translate this expression as start from i=1 then go all the way to N while on your way generate pairs that will start with atleast one value greater than i.
To understand this statement, imagine you are given the task of watering the trees on the sides of a road, as you proceed on the road the number of trees increases at a particular point by one, now there are several points on the road and you have to water the plants in such a way that the point no. on which you are standing, the no. of trees on that point to be watered will be atleast one greater than the point no.
Now, we just need to implement the same idea in code.
After getting the combo check whether the combo sum divides the combo multiplication.
.
Full C++ implementation/Code :
using namespace std;
int main() {
int n; cout<<"Enter the value of n "; cin>>n; int i,j; int array1[n*(n-1)/2]; for(i=1; i<=n; i++) { for(j=i+1; j<=n; j++) { if((i*j)%(i+j) == 0) { cout<<i<<" + "<<j<<" divides "<<i<<" * "<<j<<endl; } } }
return 0;
}
Sample INPUT/OUTPUT :
N = 15
N = 80
N = 69
