当前位置: 代码迷 >> 综合 >> Project Euler problem 45
  详细解决方案

Project Euler problem 45

热度:43   发布时间:2024-01-13 17:37:07.0


观察一下就发现。  只要满足第3个序列 ,一定会有第一个序列


所以搜第3个序列,看满足第二个序列不。


对于第n项的第3个序列。值为m = (2 * n  - 1) * n

然后就要找一个第二序列的项x 使得 x * (3 *x - 1) = 2 * m

可以发现x 的下界和上界分为sqrt(2* m / 3)和sqrt(2 * m/ 3) + 1 

然后看能不能搞就行了

注意有可能超int

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <stack>
#include <cmath>
#define eps 1e-6
#define INF 1000000007
#define PI acos(-1.0)
using namespace std;
bool gao(long long x)
{int m = (int)sqrt(x / 3) + 1;int n = (int)sqrt(x / 3);for(int i = n; i <= m; i++){if(x % i == 0){int t = x / i;if(t == 3 * i - 1) return 1;}}return 0;
}
int main()
{for(int i = 144; ; i++){long long tmp = (long long)(2 * i - 1) * 2LL * (long long)i;if(gao(tmp)){printf("%I64d\n", (long long)i * (long long)(2 * i - 1));break;}}return 0;
}


  相关解决方案