\(\mathrm{O}(N \sqrt{N})\) 解法

\(A,B,C,D\) としてあり得るもの全てについて \(AB+CD=N\) を満たすかどうかを調べると \(\mathrm{O}(N^4)\) で答えを求められますが、これは実行時間制限に対して遅すぎます。\(A,B,C\) の値を仮定すると \(AB+CD=N\) を満たす \(D\) は高々 \(1\) 個であり、\(N-AB\) がせいかつ \(C\) の倍数かどうかを調べることで存在するかどうかも判定出来るため、\(A,B,C\) を全探索することで \(\mathrm{O}(N^3)\) になりますが、これもやはり遅すぎます。
\(AB\) の値を \(X\) と仮定すると、\(CD\) の値 \(Y\) は \(N-X\) と定まります。また、先ほどと同様の論理で \(A\) の値を仮定すると \(B\) の値が、\(C\) の値を仮定すると \(D\) の値が定まります。\(X\) の値、\(A\) の値、\(C\) の値を全探索すると先ほどと同様 \(\mathrm{O} (N^3)\) となりますが、\(X=AB\) を満たす \(A,B\) の個数、および \(Y=CD\) を満たす \(C,D\) の個数は独立に求められるため、\(\mathrm{O}(N^2)\) で求められます。また、\(A\leq B\) と仮定すると \(X=AB\) を満たす \(A\) は\(A \leq \sqrt{X}\) を満たすため、( \(C,D\) も同様に調べることで) \(\mathrm{O}(N \sqrt{N})\) で答えを求められます。

実装例 (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)\) 解法

\(AB=X\) を満たす正整数 \(A,B\) の個数は \(X\) の正の約数の個数に等しいです。また、正の整数 \(x\) に対し、\(x\) を約数に持つ正の整数は \(x,2x,3x,\ldots\) です。このため、長さ \(N\) の配列を用意し、\(x=1,2,\ldots\) に対して添え字が \(x\) の倍数の値を \(1\) 増やす、という処理をすることで各値が何個約数を持つかを求めることが出来ます。
また、上の加算処理は各 \(x\) に対して \(\frac {N}{x}\) 回程度行われるため、全体では \(\frac{N}{1} + \frac{N}{2} + \ldots + \frac{N}{N}\) 回程度行われます。これは \(\mathrm{O}(N \log N)\) と評価出来ることが知られており(調和級数と調べると出てきます)、先の \(\mathrm{O}(N \sqrt{N})\) 解法よりも高速に動作します。