欧拉计划 Project Euler 27 题解

题干

思路

可以先筛1e6的素数出来然后暴力找即可，具体思路看代码

code

#include <bits/stdc++.h>using namespace std;using ll = long long;const int N = 1e6 + 5;
bool vis[N];
int pri[N];void getPrime() {memset(vis, true, sizeof(vis));vis[1] = false;int k = 1;for (int i = 2; i <= N; ++i) {if (vis[i]) pri[k++] = i;for (int j = 1; j <= k && i * pri[j] <= N; ++j) {vis[i * pri[j]] = false;if (i % pri[j] == 0) break;}}
}void solve() {getPrime();int ans = 0, t = 0;int x, y;for (int a = -999; a < 1000; ++a) {for (int b = -1000; b <= 1000; ++b) {int cnt = 0, f;do {f = cnt * cnt + a * cnt + b;cnt++;} while (f > 1 && vis[f]);if (cnt > t) {ans = a * b;x = a;y = b;t = cnt;}}}cout << x << " " << y << " " << t << "\n";cout << ans << "\n";}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int tt = 1; // cin >> tt;while (tt--) {solve();}return 0;
}