题解 | #Math#

E - Math

题意： 求的答案

题解： 打表找规律，找到两种

• 第一种是形如这样的二元组，预处理内的立方即可
• 第二种是一个递推的关系, 也预处理一下即可
• 计算过程中会爆，开__int128即可

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define dbg(x...) do{ cout << #x << " -> "; err(x);} while (0)
void err() { cout << endl;}
template<class T, class ...Ts> void err(const T& arg, const Ts&... args) { cout << arg << " "; err(args...);}

typedef long long ll;
const int maxn = 1e6 + 7;
ll a[maxn], n, b[maxn];

void run(int n) {
    int ans = 0;
    printf("n -> %d\n", n);
    for(int i = 1; i <= n; i++) {
        for(int j = i; j <= n; j++)
            if((i * i + j * j) % (i * j + 1) == 0) {
                if(i * i * i != j)
                    printf("(%d,%d)\n", i, j);
                ans++;
            }
    }
    printf("%d\n", ans);
    puts("*************");
} 

void solve() {
    scanf("%lld", &n);
    int idx1 = upper_bound(a + 1, a + 1000001, n) - a - 1;
    int idx2 = upper_bound(b + 1, b + 4587 + 1, n) - b - 1;
    ll ans = idx1 + idx2;
    printf("%lld\n", ans);
}

void init() {
    int num = 0;
    __int128 now = 0, pre = 0, nxt = 0, bas = 0;
    for(__int128 i = 2; i <= 1000000; i++) {
        now = i * i * i;
        pre = i * i;
        bas = i;
        while(1) {
            nxt = pre * now - bas;
            if(nxt > 1000000000000000000)
                break;
            b[++num] = (ll)nxt;
            bas = now;
            now = nxt;
        }
    }
    sort(b + 1, b + 1 + 4587);
}

int main() {
    int t = 1;
    for(ll i = 1; i <= 1000000; i++)
        a[i] = i * i * i;
    init();
    scanf("%d", &t);
    while (t--) solve();
//    for(int i = 10000; i <= 10000; i++)
//        run(i);
    return 0;
}