WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #183 Div2 A "Pythagorean Theorem II"

問題

http://codeforces.com/contest/304/problem/A

数学の世界では、ピタゴラスの定理ユークリッド幾何学における直角三角形の3辺の関係性である。この定理は次のようなものになる

どんな直角三角形においても、
斜辺(最も長い辺)を1辺とした正方形の面積は、
その他の辺を1辺とした正方形の面積の合計と等しくなる。

この定理は3辺をa, b, cとすると、
俗にピタゴラスの方程式と呼ばれる、
下記のような等式で表す事ができる。

a^2 + b^2 = c^2

ここのおける c は斜辺の長さであり、
a, bはその他の2辺の長さである。

nが与えられるので、3辺の長さをa, b, cとしたとき、1 <= a <= b <= c <= nを満たすような、直角三角形の数を数えよ。

制約

1 <= n <= 10000


考えた事

aとbで全探索しても、実は10000 * 10001 / 2で約5000万だからいけちゃうんじゃないかしら。


ソースコード

int main() {

    int n;
    cin >> n;

    int ans = 0;
    for( int a = 1; a <= n - 2; a++ ){
        for( int b = a; b <= n - 1; b++ ){
            int c_pow = a * a + b * b;
            int c = (int)sqrt((double)c_pow);
            if( c * c == c_pow && c <= n ){
                ans++;
            }
        }
    }

    cout << ans << endl;
}