Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-05-03

[][] Project Euler Problem 75 12:27 はてなブックマーク -  Project Euler Problem 75 - 練習帳

問題文

 http://projecteuler.net/index.php?section=problems&id=75

要約

 1 本の針金を折り曲げて,各辺の長さが整数の直角三角形をつくる.長さが1500000 以下で,作れる直角三角形が 1 種類しかないものの個数を求めよ.

方針

 3辺の長さが互いに素ならば,その3辺は適当な正数m>nを用いて,m^{2} + n^{2}, m^{2} - n^{2}, 2mnと表せる.従って,これを整数倍したものを数え上げれば良い.互いに素な3辺を上のように表す(m, n) は一意的だが,3辺を整数倍して,k (m^{2} + n^{2} ), k *( m^{2} - n^{2} ), k * 2mnというものをすべて数え上げるとダブりが生じてしまう.例えば,

(m, n, k) → (作られる3辺) 
(2, 1, 2) →  (10, 8, 6)
(3, 1, 1) →  (10, 6, 8)

 下のコードでは,3辺を長い順にソートし表示が一意的になるようにし,set を用いて既に現れた組はものを追加しないようにしている.

コード例(C++)

実行時間は11秒程度でした

#include <iostream>
#include <map>
#include <set>
#include <utility>

using namespace std;

static const int N = 1500000;
map<int , set<pair<int ,pair<int,int> > > > l;

int main(){
  for(long long  m = 1; (2 * m * (m+1) ) < N; m++){
    for(long long  n = 1; n < m &&  (2 * m * (m+n) ) < N; n++){
      for(long long k = 1; (2 * m * (m+n) ) * k < N; k++){
	int a = k * (m * m + n * n);
	int b = k * (m * m - n * n);
	int c = k * (2 * m * n);
	if(b < c) swap(b,c);
	l[a+b+c].insert(l[a+b+c].end(), make_pair(a, make_pair(b,c)));
      }
    }    
  }

  int ans = 0;
  
  typedef map<int , set<pair<int ,pair<int,int> > > >::const_iterator ittype;
  for(ittype it = l.begin(); it != l.end() ;it++){
    if((it->second).size() == 1){
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}