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; }