Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1004-595fbec3
この記事にトラックバックする(FC2ブログユーザー)

SRM247 DIV2 MEDIUM - FracCount (この記事を編集する[管理者用])

Source

TopCoder SRM247 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

a/bという分数が与えられるので,それは
 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, ...
という0より大きく1より小さい既約分数を並べた列の何番目に出てくるかを求める問題.
aとbは1000以下で,GCD(a,b)=1であることは保証されている.

解法

やるだけ.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

int GCD(int a,int b){int r; while(a){r=b; b=a; a=r%a;} return b;}

class FracCount {
public:
int position(int numerator, int denominator) {
  int i,j,res=0;

  for(i=2;;i++) for(j=1;j<i;j++){
    if(GCD(i,j)!=1) continue;
    res++;
    if(i==denominator && j==numerator) return res;
  }
  
  return -1;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1004-595fbec3
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。