TIOJ 1309：幾組解咧(其二)

TIOJ 1309：幾組解咧(其二)

題目大意：有個函數 $f(s,t,u,v) = as^p+bt^q+cu^r+dv^w$，且 $-1000≤a,b,c,d≤1000，1≤p,q,r,w≤3，0≤s,t,u,v≤1000$。問有多少組 $(s,t,u,v)$ 可滿足 $f(s,t,u,v)=0$ ?

解法：首先純數學解我顯然不知道，這時候可以考慮枚舉，但是 $1000^4$ 太大了，其實可以先把左半邊的 $1000^2$ 算好，再用右半邊的去加上左半邊的，可用一個 $\text{unordered_map}$ 紀錄。只是這題空間卡很緊，在加上左半邊東西的時候，不能直接詢問，不然大小會變兩倍大，而是先把位置找出來再去算。我看到蠻多人記憶體都在 $10000\ \text{KB}$ 以內，不知道是怎麼做到的。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

unordered_map<long long, int> cnt;

long long power (int d, int up) {
    return up == 1 ? d : up == 2 ? d * d : d * d * d;
}

void solve() {
    int a, b, c, d, p, q, r, w;
    long long ans = 0;
    cin >> a >> b >> c >> d >> p >> q >> r >> w;
    cnt.clear();
    FOR (s, 0, 1000) FOR (t, 0, 1000) cnt[a * power (s, p) + b * power (t, q)]++;
    FOR (u, 0, 1000) FOR (v, 0, 1000) {
        long long t = -c * power (u, r) - d * power (v, w);
        auto it = cnt.find (t);
        if (it != cnt.end()) {
            ans += it->S;
        }
    }
    cout << ans << '\n';
}

int main() {
    Waimai;
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！