Skip to content

12110: 【原2110】方程解数

题目

题目描述

author: cby1992 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/2110

Description

\(A_1 \times {x_1}^3+A_2 \times {x_2}^3+A_3 \times {x_3}^3+A_4 \times {x_4}^3+A_5 \times {x_5}^3 = 0\)。

\(x_1,x_2,x_3,x_4,x_5\)都是在区间[\(-limit,limit\)]之间的整数,且\(x_1,x_2,x_3,x_4,x_5\)都不等于\(0\)。

给定\(A_1,A_2,A_3,A_4,A_5\),问\(x_1,x_2,x_3,x_4,x_5\)共有多少种可能的取值?

Input Format

输入共有\(1\)行\(6\)个整数:\(A_1,A_2,A_3,A_4,A_5,limit\)。

Output Format

输出\(1\)行\(1\)个整数:取值方案数。

Sample Input

37 29 41 43 47 50

Sample Output

654

Specification

对于全部数据:\(-50 \leq A_i \leq 50; 1 \leq limit \leq 50\)

对于50%的数据: \(1 \leq limit \leq 20\)

对于30%的数据:\(1 \leq limit \leq 10\)

Hint

标准方法使用Hash表,注意输出超int的情况。

zqy2018's solution

/*
    Hint: meet in the middle
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int a[10], lim;
unordered_map<int, int> mp;
inline int cub(int x){
    return x * x * x;
}
void init(){
    for (int i = 1; i <= 5; ++i)
        a[i] = read();
    lim = read();
    for (int i = -lim; i <= lim; ++i){
        if (!i) continue;
        int r1 = a[1] * cub(i);
        for (int j = -lim; j <= lim; ++j){
            if (!j) continue;
            int r2 = a[2] * cub(j);
            for (int k = -lim; k <= lim; ++k){
                if (!k) continue;
                int r3 = a[3] * cub(k);
                if (!mp.count(r1 + r2 + r3))
                    mp[r1 + r2 + r3] = 0;
                ++mp[r1 + r2 + r3];
            }
        }
    }
}
void solve(){
    ll ans = 0;
    for (int i = -lim; i <= lim; ++i){
        if (!i) continue;
        int r1 = -a[4] * cub(i);
        for (int j = -lim; j <= lim; ++j){
            if (!j) continue;
            int r2 = -a[5] * cub(j);
            if (mp.count(r1 + r2))
                ans += mp[r1 + r2];
        }
    }
    printf("%lld\n", ans);
}
int main(){
    init();
    solve();
    return 0;
}