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