题目大意

求出有多少对四元组 $(A,B,C,D)$ 满足 $AB+CD=N$

思路

首先有一个最直接的思路是去枚举四个变量，时间复杂度 $O(n^4)$，显然是不能通过的。考虑优化。我们可以发现，如果确定了 $AB$ 的值那么 $CD$ 自然确定。那尝试枚举 $AB$ 的值。之后我们要确定每组 $AB$ 里面有多少种可能。根据我们学过的约数很明显这就是两个约数之和。那么我们枚举每一组的约数个数即可。然后我们将 $AB$ 的约数个数乘以 $2$，由于 $A,B$ 并不相等，所以要换位。但是要注意如果 $\sqrt{AB}$ 是整数的话要 $-1$，原因显然。之后 $CD$ 同理。之后将这两个值相乘即可。

代码

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
ll n;
int main(){
    cin>>n;
    ll ans=0;
    for (int i = 1; i <n ; ++i) {
        ll j=n-i,num1=0,num2=0;
        for (int k = 1; k*k<=i ; ++k) {
            if(i%k==0){
                num1++;
            }
        }
        num1*=2;
        if(sqrt(i)==ll(sqrt(i))){
            num1--;
        }
        for (int k = 1; k*k<=j ; ++k) {
            if(j%k==0){
                num2++;
            }
        }
        num2*=2;
        if(sqrt(j)==ll(sqrt(j))){
            num2--;
        }
        ans+=num1*num2;
    }
    cout<<ans<<endl;
    return 0;
}