C - Four Variables Editorial by en_translator
\(\mathrm{O}(N \sqrt{N})\) Solution
We can exhaustively enumerate all \((A,B,C,D)\) and check if \(AB+CD=N\) to find the answer in a total of \(\mathrm{O}(N^4)\) time, but it is too slow for the execution time limit. For a fixed \((A,B,C)\), there is at most one \(D\) such that \(AB+CD=N\), which can be determined by checking if \(N-AB\) is non-negative and is a multiple of \(C\), so we can find the answer by exhaustively enumerating \((A,B,C)\) in a total of \(\mathrm{O}(N^3)\) time, but this is too slow as well.
When the value \(AB\) is fixed to \(X\), the value \(CD\), which we denote by \(Y\), is determined to be \(N-X\). As we described above, fixing \(A\) determines \(B\), and \(C\) determines \(D\). By exhaustively searching all values for \(X\), \(A\), and \(C\), the cost is still \(\mathrm{O} (N^3)\); however, we can find the number of \((A,B)\) such that \(X=AB\) and \((C,D)\) such that \(Y=CD\) independently, so it can be reduced to \(\mathrm{O}(N^2)\). Moreover, if we assume \(A\leq B\), the value \(A\) such that \(X=AB\) satisfies \(A \leq \sqrt{X}\), and same holds for \(C\) and \(D\). Thus, the problem can be solved in a total of \(\mathrm{O}(N \sqrt{N})\) time.
Sample code (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
cin>>N;
long long ans = 0;
for(int i=1;i<N;i++){
int X = i,Y = N-i;
long long x = 0,y = 0;
for(int j=1;j*j<=X;j++){
if(X%j==0){
x++;
if(X!=j*j)x++;
}
}
for(int j=1;j*j<=Y;j++){
if(Y%j==0){
y++;
if(Y!=j*j)y++;
}
}
ans += x * y;
}
cout<<ans<<endl;
return 0;
}
\(\mathrm{O}(N \log N)\) solution
The number of pairs of positive integers \((A,B)\) such that \(AB=X\) equals the number of positive divisors of \(X\). Also, for a positive integer \(x\), the integers whose positive divisors contain \(x\) are \(x,2x,3x,\ldots\). Thus, one can count the number of divisors of each value by preparing a length-\(N\) array and increment the elements whose indices are multiples of \(x\).
The increment happens about \(\frac {N}{x}\) times for each \(x\), for a total of about \((\frac{N}{1} + \frac{N}{2} + \ldots + \frac{N}{N})\) times. It is known that we can evaluate it as \(\mathrm{O}(N \log N)\) (which is called the harmonic series), so this solution is faster than the \(\mathrm{O}(N \sqrt{N})\) solution above.
posted:
last update: