Subtask ~1~: Giả sử một người có ~x~ đồng. Người đó sẽ chỉ sử dụng hết được số tiền đó khi họ mua đúng ~y~ con búp bê (hoặc lego) giá ~z~ đồng sao cho ~y * z = x~.

Vì vậy, ta sẽ dùng ~1~ vòng lặp từ ~1~ đến ~n-1~ để chia ~i~ đồng cho Alob, và ~n-i~ đồng cho Bice. Ta sẽ dùng thêm 1 vòng lặp từ ~1~ đến ~i~ để đếm số cách Alob mua được hết số tiền của mình, và một vòng lặp tương tự từ ~1~ đến ~n-i~ cho Bice.

Độ phức tạp ~O(n^3)~.

Subtask ~2~:

Dễ chứng minh để ~y * z = x~ thì ~y~ và ~z~ đều phải là ước của ~x~. Vì vậy ta có thể chuẩn bị trước kết quả cho mỗi giá trị ~x~ để loại bỏ ~2~ vòng lặp của Alob và Bice.

Gọi ~f[i]~ là số cách mua khi một người có ~i~ đồng, và ~f[i]~ là số ước của ~i~.

Đáp án: ~\sum\limits_{i = 0}^{n}(f[i] \times f[n-i])~.

Độ phức tạp ~O(n)~.

Code mẫu

#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for (ll i=m;i<=n;i++)
#define reb(i,m,n) for (ll i=m;i>=n;i--)
#define rv(i,vt) for (auto i:vt)
#define ii pair<ll,ll>
#define vi vector<ll>
#define F first
#define S second
#define pb push_back
#define sz(v) (ll)v.size()
#define iii tuple<ll,ll,ll>
using namespace std;
const ll N=1e6+5,mod=1e9+7;
ll f[N+5],n;
void elixprep(){
    rep(i,1,N)
    for (ll j=i;j<=N;j+=i) f[j]++;
}
void elix()
{
    cin>>n;
    ll res=0;
    rep(i,1,n-1) res+=f[i]*f[n-i];
    cout<<res;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll tests=1;
    //cin>>tests;
    elixprep();
    while (tests--){
        elix();
        cout<<endl;
}
    cerr << "\n" << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
}
//listen to trap music. it won't help