题解：UVA13262 Count Equation Solutions

Public_leda_team · 2024-09-24 14:40:46 · 题解

这道题直接暴力枚举是 O(m^6) 的，显然会超时。

那么我们考虑将式子分为 a_1x_1-a_2x_2+a_3x_3 和 -a_4x_4+a_5x_5-a_6x_6 两个部分，前面的部分可以 O(m^3) 枚举，后面的的部分直接查询相反数即可。

时间复杂度 O(m^3)。

#include <iostream>
#include <unordered_map>
// #define int long long
using namespace std;
int m, a[7];
unordered_map<int, int> mp;
signed main() {
  // ios::sync_with_stdio(0);
  // cin.tie(0), cout.tie(0);
  while (scanf("%d", &m) != -1) {
    mp.clear();
    for (int i = 1; i <= 6; ++i) {
      scanf("%d", &a[i]);
    }
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= m; ++j) {
        for (int k = 1; k <= m; ++k) {
          mp[a[1] * i - a[2] * j + a[3] * k]++;
        }
      }
    }
    long long ans = 0;
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= m; ++j) {
        for (int k = 1; k <= m; ++k) {
          ans += mp[-(-a[4] * i + a[5] * j - a[6] * k)];
        }
      }
    }
    printf("%lld\n", ans);
  }
}