PROBLEM LINK:
Setter: Daanish Mahajan
Tester: Manan Grover
Editorialist: Ajit Sharma Kasturi
DIFFICULTY:
Easy-medium
PREREQUISITES:
PROBLEM:
Given a positive integer N, we need to find the number of tuples (A,B,C,D) where 1 \leq A,B,C,D \leq N and {A} \cdot {B} = {C} \cdot {D}.
QUICK EXPLANATION:
-
This problem is equivalent to finding the number of tuples (A,B,C,D) where 1 \leq A,B,C,D \leq N and \frac{A} {B} = \frac{C}{D}.
-
The number of tuples (A,B,C,D) for which A=B and \frac{A}{B} = \frac{C}{D} will be N^2.
-
If we find the number of tuples (A,B,C,D) for which A\geq B,( let this be x ), we can also find the final answer which will be 2\cdot x - N^2.
-
Every fraction \frac{A}{B} can be reduced into a unique irreducible fraction \frac{X}{Y} i.e, GCD(X,Y)=1.
-
In order to solve the case for X \geq Y, we can iterate over every X from 1 to N and add \phi(X) \cdot \lfloor \frac{N}{X} \rfloor \cdot \lfloor \frac{N}{X} \rfloor to the answer where \phi is the euler totient function. This is because the number of Y for which GCD(X,Y)=1 is \phi(X) and each of the irreducible fraction \frac{X}{Y} contributes \lfloor \frac{N}{X} \rfloor \cdot \lfloor \frac{N}{X} \rfloor fraction pairs to the answer.
EXPLANATION:
Let us consider the equation A\cdot B = C \cdot D . This equation can be rewritten as follows: \frac{A}{C}=\frac{D}{B}. Therefore, we can reformulate the problem as follows: Given a positive integer N, we need to find the number of tuples (A,B,C,D) where 1 \leq A,B,C,D \leq N and \frac{A}{B} = \frac{C}{D}. The answer for this problem must be the same as the answer for our original problem.
The number of fractions \frac{A}{B} for which A=B will be N. They are \frac{1}{1}, \frac{2}{2}, \frac{3}{3}, \dots \frac{N}{N}. Therefore, the number of tuples (A,B,C,D) where A=B and \frac{A}{B} = \frac{C}{D} will be the number of pairs we can form with these N fractions which is N \cdot N.
Let us solve the case for A \geq B . Let this be x. Then, by symmetry, the number of tuples (A,B,C,D) for A \leq B will also be x. Therefore, our final answer will then be
x+x - ( number of tuples (A,B,C,D) where A=B and \frac{A}{B} = \frac{C}{D} )
= x+x-(N \cdot N)
=2 \cdot x-(N \cdot N).
Therefore, we could easily find the final answer if we have the answer for the case A \geq B.
The most crucial property of \frac{A}{B} = \frac{C}{D} is that both \frac{A}{B} and \frac{C}{D} can be reduced to a unique irreducible fraction \frac{X}{Y} i.e, GCD(X, Y) = 1.
Thus if we go through every irreducible fraction \frac{X}{Y} where X \geq Y and calculate the number of tuples (A,B,C,D) where \frac{A}{B} = \frac{C}{D} = \frac{X}{Y}, then we are done.
The number of fractions which are equal to \frac{X}{Y} is \lfloor \frac{N}{X} \rfloor. They are \frac{X}{Y}, \frac{2 \cdot X}{2 \cdot Y}, \frac{3 \cdot X}{3 \cdot Y}, \dots \frac{\lfloor \frac{N}{X} \rfloor \cdot X}{\lfloor \frac{N}{X} \rfloor \cdot Y} .
The number of pairs we can make from these fractions are \lfloor \frac{N}{X} \rfloor \cdot \lfloor \frac{N}{X} \rfloor .
Let us fix some X, and let tot be the number of possible Y where X \geq Y and gcd(X, Y)=1. Clearly, tot = \phi(X) where \phi is the euler-totient function. We can precompute the values of \phi(X) for all 1 \leq X \leq N.
The number of irreducible fractions \frac{X}{Y} where X \geq Y is \phi(X) and each of them contribute \lfloor \frac{N}{X} \rfloor \cdot \lfloor \frac{N}{X} \rfloor to the answer.
From this information we can calculate the answer for the case A \geq B as follows:
Iterate over X from 1 to N and add \phi(X) \cdot \lfloor \frac{N}{X} \rfloor \cdot \lfloor \frac{N}{X} \rfloor to the answer.
By calculating the answer for A \geq B, we can easily find the total number of tuples (A,B,C,D) for which \frac{A}{B} = \frac{C}{D} as explained above.
TIME COMPLEXITY:
O(N \log N) or O(N \log \log N) depending on the implementation for precomputation of \phi values.
SOLUTION:
Editorialist's solution
#include <bits/stdc++.h>
using namespace std;
int phi[1000005]; // Euler totient function phi
void precompute(int n)
{
phi[1] = 1;
for (int i = 2; i <= n; i++)
phi[i] = i - 1;
for (int i = 2; i <= n; i++)
{
//Based on the divisor sum property of phi
for (int j = 2 * i; j <= n; j += i)
phi[j] -= phi[i];
}
}
int main()
{
precompute(1000000);
int tests;
cin >> tests;
while (tests--)
{
int n;
cin >> n;
long long int ans = 0;
for (int i = 1; i <= n; i++)
{
ans += (1LL * phi[i] * (n / i) * (n / i));
}
ans = 2 * ans - 1LL * n * n;
cout << ans << endl;
}
return 0;
}
Setter's solution
#include <bits/stdc++.h>
#define int long long
//#include <sys/resource.h>
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
#define MOD 1000000007
#define INF 1000000000
#define mid(l, u) ((l+u)/2)
#define rchild(i) (i*2 + 2)
#define lchild(i) (i*2 + 1)
#define mp(a, b) make_pair(a, b)
#define lz lazup(l, u, i);
using namespace std;
const int N = 1e6 + 5;
int phi[N];
signed main() {
phi[0] = 0;
phi[1] = 1;
for (int i = 2; i < N; i++) phi[i] = i;
for (int i = 2; i < N; i++) {
if (phi[i] == i) {
for (int j = i; j < N; j += i)
phi[j] -= phi[j] / i;
}
}
int t;
cin>>t;
assert(1<=t && t<=10);
while(t--){
int n;
cin>>n;
assert(1<=n && n<=1e6);
int ans = n*n;
for(int q = 2;q<=n;q++){
int poss = (n/q);
poss *= poss;
poss *= phi[q]*2;
ans += poss;
}
cout<<ans<<endl;
}
return 0;
}
Tester's solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1000001
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
ll dp[N] = {};
for(int i = 1; i < N; i++){
dp[i] = 2 * i - dp[i];
for(int j = 2 * i; j < N; j += i){
dp[j] += dp[i];
}
}
int t;
cin>>t;
while(t--){
ll n;
cin>>n;
ll ans = 0;
for(int i = 1; i < n + 1; i++){
ll k = n / i;
ans += k * k * dp[i];
}
ans -= n * n;
cout<<ans<<"\n";
}
return 0;
}
Please comment below if you have any questions, alternate solutions, or suggestions. 