欧拉计划45题

Triangular, pentagonal, and hexagonal

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle $T_n = n * (n + 1) / 2$         1,3,6,10,15,…

Pentagonal        $P_n = n *(3 * n - 1) / 2$ 1,5,12,22,35,…

Hexagonal         $H_n = n * (2 * n - 1)$      1,6,15,28,45,…

It can be verified that $T_{285} = P_{165} = H_{143}$ = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

三角形数、五边形数和六边形数

三角形数、五边形数和六边形数分别由以下公式给出：

三角形数五边形数六边形数

三角形数         $T_n = n * (n + 1) / 2$         1,3,6,10,15,…

五边形数         $P_n = n *(3 * n - 1) / 2$ 1,5,12,22,35,…

六边形数         $H_n = n * (2 * n - 1)$      1,6,15,28,45,…

可以验证， $T_{285} = P_{165} = H_{143}$ =40755。

找出下一个同时是三角形数、五边形数和六边形数的数。

这个题目，每个函数都是单调递增的，所以可以用二分法来进行解决，比如求出三角形数，然后利用二分法去查找五边形数和六边形数的n；时间复杂度为O(logn)级别；

我准备还是用反函数去求，这样时间复杂度为O(1)，这样可以节省更多时间；那么他们分别对应的反函数是：

三角形： $n = sqrt(2 * t + 1/4) - 1/2 = (sqrt(8 * t + 1) - 1) / 2$

五边形:    $n = sqrt(2 * p / 3 + 1 / 36) + 1/ 6 = (sqrt(24 * p + 1) + 1) / 6$

六边形:    $n = sqrt(h / 2 + 1 / 16) + 1/4 = (sqrt(8 * h + 1) + 1) / 4$

这下又了对应的反函数，那么写代码的思路也没有一点问题，下面的代码实现：
#include <stdio.h>
#include <math.h>

typedef long long ll;

ll Hexagonal(int n) {//六边形对应函数
    return n * (2 * n - 1);
}

int inverse_Triangle(ll x) {//三角形的反函数
    double s = (sqrt(8.0 * x + 1.0) - 1.0) / 2.0;
    if (s != floor(s)) return 0;
    return 1;
}

int inverse_Pentagonal(ll x) {//五边形的反函数
    double s = (sqrt(24 * x + 1.0) + 1.0) / 6.0;
    if (s != floor(s)) return 0;
    return 1;
}


int main() {
    for (int i = 144; i; i++) {
        ll num = Hexagonal(i);
        if (!inverse_Triangle(num)) continue;
        if (!inverse_Pentagonal(num)) continue;
        printf("%lld\n", num);
        break;
    } 
    return 0;
}

二分的话，我直接把代码写出来把过程就不推导了；

#include <stdio.h>

typedef long long ll;

ll Triangle (ll n) {
    return n * (n + 1) / 2;
}

ll Pentagonal (ll n) {
    return n * (3 * n - 1) / 2;
}

ll Hexagonal (ll n) {
    return n * (2 * n - 1);
}

int func(int l, int r, ll x, ll (*func)(ll)) { 
    ll mid;
    while (r >= l) {
        mid = (r + l) >> 1;
        ll num = func(mid);
        if (num == x) return 1;
        else if (num > x) r = mid - 1;
        else l = mid + 1;
    }
    return 0;
}
 

int main() {
    for (int i = 286; i; i++) {
        ll num = Triangle(i);
        if (!func(0, i, num, Pentagonal)) continue;
        if (!func(0, i, num, Hexagonal)) continue;
        printf("%lld\n", num);
        break;
    }
    return 0;
}