Link

T399753 counting problem（计数问题）

Question

给出一个正整数 \(n\) ，求 \(AB+CD=n\) 的方案数， \(A,B,C,D\) 都是要求是正整数

Solution

考虑直接枚举 \(ABCD\) 显然是不切实际的

那么就折半枚举

设 \(F_i\) 表示两个数的乘积为 \(i\) 的方案数

答案就是 \(\sum\limits_{i=1}^{n} F_i \times F_{n-i}\)

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
typedef long long LL;
LL F[maxn],ans;
int N;
int main(){
    cin>>N;
    for(int i=1;i<=N;i++){
        for(int j=1;j*i<=N;j++){
            F[i*j]++;
        }
    }
    for(int i=1;i<=N;i++){
        ans+=F[i]*F[N-i];
    }
    cout<<ans<<endl;
    return 0;
}