Project Euler - Problem 210

Obtuse Angled Triangles

Problem 210 (日本語訳)

|x| + |y| ≦ r をみたす格子点の集合を S(r) とする．

O(0, 0)，C(r/4, r/4) とする．S(r) の要素 B で，三角形 OBC が鈍角三角形となるようなものの個数を N(r) とする．

たとえば，N(4) = 24, N(8) = 100．

N(1,000,000,000) はいくつか？

図です

結局問題は円の内部にある格子点の数になりそうです．

さらに図ですが，対称性より網掛けした扇形内部の格子点を数え上げて 8 倍すればいい．

ちゃんとカウントする必要があるのは濃いめに塗られた領域だけであることを考慮すると計算がらくになります．

数がでかいと sqrt が仕事をサボるのでその辺に気をつけましょう．

あとは円外部の点をカウントしたり直線上の点の重複を除いたり色々やっておわりです．

#include <iostream>
#include <time.h>

using namespace std;
typedef long long int lint;

// r^2 < x となる最大の r
lint hoge(lint x)
{
    lint sq = (lint)sqrt(x);
    for (lint r = sq - 1; r <= sq + 1; r++) {
        if (r * r >= x) return r - 1;
    }
}

void PE0210()
{
    const lint r = (lint)125000000;

    lint count = 0;

    for (lint y = r + 1; y * y < r * r * 2; y++) {
        count += hoge(r * r * 2 - y * y);
    }

    count += r * (r - 1) / 2;

    count *= 8;

    count += (lint)floor(r * sqrt(2)) * 4 + (r - 1) * 4 + 1;

    count += 6 * r * (16 * r + 1);
    count -= 8 * r - 1;

    cout << count << endl;
}

int main()
{
    clock_t start, end;
    start = clock();

    PE0210();

    end = clock();
    printf("%d msec.\n", end - start);

    return 0;
}

5 秒くらい．