Project_Euler-44 題解

題目

思路

題目給出了一個性質，讓我在對應性質的數據中找出目標值，這種問題首先想到的就是枚舉。

我們可以枚舉 $P_k$ ，對于每一個 $P_k$ ，我們再枚舉 $P_j$，$P_j$ 從 $P_k?1$ 開始倒著往回枚舉，在枚舉的過程中，判斷他們的和差是否均為五邊形數。如果是，再與之前的已經找到的答案進行比較，如果比答案更小，說明可以取。

還有一個問題，$P_k$枚舉的范圍怎么確定？

假設我們枚舉兩個相鄰的五邊形數 $P_k$ 和 $P_{k?1}$ ， 會發現，他們的差值隨著 $k$ 的增大而不斷增大，而我們的 $P_j$ 又是從 $P_{k?1}$ 開始向前枚舉的，因此，如果相鄰的 $P_k$ 和 $P_{k?1}$ 已經大于目前已知的 $D$，那么我們再枚舉就沒有意義了，因為后面找到的答案一定大于 $D$。

對于內層循環，其實也可以使用類似的原理來做優化，如果 $P_k?P_j>D$ ，那么也不用繼續枚舉了，因為 $P_k?P_j$ 只會越來越大。

代碼

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <inttypes.h>typedef long long ll;ll pentagonal(ll n) {return (n * (3 * n - 1)) >> 1;
}ll is_pentagonal(ll x, ll n) {ll head = 1, tail = n, mid;while (head <= tail) {mid = (head + tail) >> 1;if (pentagonal(mid) == x) return 1;if (pentagonal(mid) < x) head = mid + 1;else tail = mid - 1;}return 0;
}int main() {ll ans = INT32_MAX;ll i = 1, j = 1;while (pentagonal(i + 1) - pentagonal(i) < ans) {i += 1;j = i - 1;for (; j >= 1 && pentagonal(i) - pentagonal(j) < ans; j--) {if (!is_pentagonal(pentagonal(i) + pentagonal(j), 2 * i)) continue;if (!is_pentagonal(pentagonal(i) - pentagonal(j), 2 * j)) continue;printf("%lld --> %lld\n", pentagonal(j), pentagonal(i));ans = pentagonal(i) - pentagonal(j);}}printf("MIN D is %lld\n", ans);return 0;
}