Sum of 4 divisors

2 secs 1024 MB

この問題は半分全列挙というアルゴリズムを使い解くことができます。まず、 $A$ の約数と $B$ の約数を足して $K$ になる個数をmapに保存しておいときます。そして、 $C$ の約数と $D$ の約数を足してなる数字を全探索して、mapに保存しておいた $X-K$ の個数の合計を求めることができます。

想定解(C++)

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define pb push_back

int main(){
    ll A,B,C,D,K;
    cin>>A>>B>>C>>D>>K;
    vector<ll>P(0),Q(0),R(0),S(0);
    for(ll i=1;i*i<=A;i++){
        if(i*i==A){
            P.pb(i);
        }else if(A%i==0){
            P.pb(i);
            P.pb(A/i);
        }
    }
    for(ll i=1;i*i<=B;i++){
        if(i*i==B){
            Q.pb(i);
        }else if(B%i==0){
            Q.pb(i);
            Q.pb(B/i);
        }
    }
    for(ll i=1;i*i<=C;i++){
        if(i*i==C){
            R.pb(i);
        }else if(C%i==0){
            R.pb(i);
            R.pb(C/i);
        }
    }
    for(ll i=1;i*i<=D;i++){
        if(i*i==D){
            S.pb(i);
        }else if(D%i==0){
            S.pb(i);
            S.pb(D/i);
        }
    }
    map<ll,ll>m;
    for(int i=0;i<P.size();i++){
        for(int j=0;j<Q.size();j++){
            m[P[i]+Q[j]]++;
        }
    }
    ll Ans=0;
    for(int i=0;i<R.size();i++){
        for(int j=0;j<S.size();j++){
            Ans+=m[K-R[i]-S[j]];
            
        }
    }
    cout<<Ans<<endl;
}