Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-05-12

[][] Project Euler Problem 64 01:02 はてなブックマーク -  Project Euler Problem 64 - 練習帳

 昨日休んだので,2日分.でも,1問は軽い問題でお茶を濁しています.

問題文

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

要約

 √N を連分数展開したものを [a[0]; a[1],... , a[i],...] と書き *1 ,さらに a[1] 以降で周期的な部分をまとめて,[a[0]; (a[1],... , a[i])] と書く.この時,i を周期と呼ぶ事にする.N <= 10000 で平方数でないもののうち,周期が奇数のものの個数を求めよ.

方針

√N = a[0] + res[0]

( res[0] = (s[0]√N + i[0]) / d[0] , 0 < res[0] < 1)

とし,それぞれの変数a, res を再起的に

1/res[j] = a[j+1] + res[j+1] 

(res[j+1] = (s[j+1]√N + i[j+1]) / d[j+1] , 0 < res[j+1] < 1)

と決めていく

例えば√7=[2;(1,1,1,4)]のように,a[i]だけ見ていても周期かどうかの判定はできない.resの情報をすべて保存しておく必要がある.

[a[0]; a[1], a[2], (a[3],... , a[18])]のように,周期が一部分のみになる可能性があるが,下のコードではそのようなものは存在しないと仮定してプログラムしている.実際それで正しい答えが得られたので,おそらく存在しないと思うのだが,証明はできていない.

コード例(C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct res{
  int s; // sqrt part
  int i; // int part
  int d; // denominator
  int N; // 
  res(int _s,int _i,int _d,int _N):s(_s), i(_i), d(_d), N(_N){};
  bool operator==(res& r){
    return s == r.s && i == r.i && d == r.d && N == r.N;
  } 
};

int gcd(int a, int b){
  if(a < b) swap(a,b);
  if(a % b == 0) return b;
  return gcd(a % b, b);
}

vector<int >period;

void onestep (vector<res> & rs){
  res r = rs[rs.size()-1];
  if(rs.size() != 1 && rs[0] == r) return;
  int newd = r.s * r.s * r.N - r.i * r.i;
  int news = r.d * r.s;  

  int k = 1;
  while(r.d * r.d * r.s * r.s * r.N > 
	( k * newd - r.d * r.i) * ( k * newd - r.d * r.i) )
    k++;  
  period.push_back(k-1);

  int newi =-r.d * r.i + (k-1) * newd;
  int g = gcd(gcd(news, newi), newd);
  res newr(news/g, newi/g , newd/g, r.N);
  rs.push_back(newr);
  onestep(rs);
}


int main(){
  int count = 0;
  int N = 10000;
  for(int i = 1; i<=N; i++){
    period.clear();
    int j = 0;
    while(j * j  < i) j++;
    if(j * j == i) continue;
    res r(1, j-1, 1, i);
    vector<res> rs(1, r);
    onestep(rs);
    if(period.size() % 2 == 1){
      cout << i <<endl;
      count++;
    }
  }
  cout << count << endl;
  return 0;
}

[][] Project Euler Problem 77 01:01 はてなブックマーク -  Project Euler Problem 77 - 練習帳

問題文

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

要約

 不定数の素数の和で表す表し方が5000通りを超えるもののうち,最小の整数を答えよ.(例えば 和が10となる足し方は次の 5 通り )

10 = 7 + 3
          5 + 5
          5 + 3 + 2
          3 + 3 + 2 + 2
          2 + 2 + 2 + 2 + 2

方針

 一番最後に追加した数と残りの合計で動的計画法をおこなう.

コード例(C++)

#include <iostream>
#include <map>
#include <utility>
#include <algorithm>

using namespace std;

map<pair<int, int> ,int> table;
typedef map<pair<int, int> ,int> ::const_iterator ittype;

int N = 5000;

bool isprime(int n){
  if(n == 0 || n == 1) return false;
  for(int i = 2; i * i <= n; i++){
    if(n % i == 0)
      return false;
  }
  return true;
}

int dp(int top, int sum){
  if(sum < 0 ) return 0;
  if(sum == 0 ) return 1;
  if(table.count(make_pair(top, sum)) > 0 ) 
    return table[make_pair(top, sum)];
  int ans = 0;
  for(int i = 0; i <= top; i++){
    if(!isprime(i)) continue;
    ans += dp(i, sum-i);
  }
  return table[make_pair(top, sum)] = ans;
}

int main(){  
  for(int i = 0 ;;i++){
    if(dp(i, i) > N){
      cout << i << " " << dp(i, i) << endl;
      return 0;
    }
  }
  return 0;
}