C++(g++ 7.5.0) 解法, 执行用时: 8ms, 内存消耗: 460K, 提交时间: 2022-10-19 19:43:43

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int f[3];
ll qsm(ll a, ll b) {
    ll s = 1;
    while (b) {
        if (b & 1) s = s * a;
        a = a * a;
        b >>= 1;
    }
    return s;
}
ll C(ll a, ll b) {
    ll s = 1;
    for (ll i = 1; i <= b; i++) {
        s = s * (a - i + 1) / i;
    }
    return s;
}
ll get(int sum, int x) {
    ll s = 1;
    for (int i = 0; i < 3; i++) {
        if (f[i] % x != 0) return 0;
        s = s * C(sum, f[i] / x);
        sum -= f[i] / x;
    }
    return s;
}
int get_phi(int x) {
    int phi = 1;
    for (int i = 2; i <= x / i; i++) {
        if (x % i == 0) x /= i, phi *= i - 1;
        while (x % i == 0) x /= i, phi *= i;
    }
    if (x > 1) phi *= (x - 1);
    return phi;
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        for (int i = 0; i < 3; i++) scanf("%d", &f[i]);
        int n = f[0] + f[1] + f[2];
        ll ans = 0;
        for (int i = 1; i <= n / i; i++) {
            if (n % i == 0) {
                ans += get_phi(i) * get(n / i, i);
                if (i != n / i) ans += get_phi(n / i) * get(i,n / i);
            }
        }
        if (n & 1) {
            for (int i = 0; i < 3; i++) {
                if (!f[i]) continue;
                f[i]--;
                ans += get((n - 1) / 2, 2) * n;
                f[i]++;
            }
        } else {
            ans += get(n / 2, 2) * n / 2;
            for (int i = 0; i < 3; i++) {
                if (!f[i]) continue;
                f[i]--;
                for (int j = 0; j < 3; j++) {
                    if (!f[j]) continue;
                    f[j]--;
                    ans += get((n - 2) / 2, 2) * n / 2;
                    f[j]++;
                }
                f[i]++;
            }
        }
        printf("%lld\n", ans / (2 * n));
    }
    return 0;
}

C++ 解法, 执行用时: 11ms, 内存消耗: 428K, 提交时间: 2022-07-12 23:39:04

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;

LL Phi(int x){
    LL phi = x;
    for(int i = 2; i <= x; i ++){
        if(x % i == 0){
            while(x % i == 0) x /= i;
            phi = 1ll * phi / i * (i - 1);
        }
    }
    return phi;
}

LL C[100][100];
void init(){
    C[0][0] = 1;
    for(int i = 1; i <= 50; i ++){
        for(int j = 0; j <= i; j ++){
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
        }
    }
}


int main(){
    int T; cin >> T;
    init();
    while(T--){
        int a, b, c; scanf("%d %d %d", &a, &b, &c);
        int n = a + b + c;
        LL res = 0;
        for(int i = 1; i <= n; i ++){
            if(n % i == 0){
                if(a / i + b / i + c / i == n / i){
                    res += 1ll * Phi(i) * C[n / i][a / i] * C[n / i - a / i][b / i];
                }
            }
        }
        if(n & 1){
            int cnt = a % 2 + b % 2 + c % 2;
            if(cnt == 1){
                res += 1ll * C[n / 2][a / 2] * C[n / 2 - a / 2][ b / 2] * n;
            }
        }
        else{
            int cnt = a % 2 + b % 2 + c % 2;
            if(cnt == 0){
                res += 1ll * C[n / 2][a / 2] * C[n / 2 - a / 2][b / 2] * n / 2;
                if(a >= 2) res += 1ll * C[n / 2 - 1][a / 2 - 1] * C[n / 2 - a / 2][b / 2] * n / 2;
                if(b >= 2) res += 1ll * C[n / 2 - 1][a / 2] * C[n / 2 - 1 - a / 2][b / 2 - 1] * n / 2;
                if(c >= 2) res += 1ll * C[n / 2 - 1][a / 2] * C[n / 2 - 1 - a / 2][b / 2] * n / 2;
            }
            else if(cnt == 2){
                res += 1ll * 2 * C[n / 2 - 1][a / 2] * C[n / 2 - 1 - a / 2][ b / 2] * n  / 2;
            }
        }
        long long ans = res / n / 2;
        cout << ans << endl;       
    }

}