Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM216 DIV1 MEDIUM - Refactoring (この記事を編集する[管理者用])

Source

TopCoder SRM216 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

整数n (2以上2*10^8以下) が与えられるので,それを2つ以上の2以上の整数の積で各方法は何通りあるかを求める問題.
順番が違うだけのものは同じとみなす.(x*yとy*xなど)

解法

サンプルにこれが最悪ケースだよと最悪ケースが書いてある.
その答えを見るかぎり全探索で間に合いそうで,実際に間に合う.

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

int solve(int n, int st){
  int i, res = 1;

  for(i=st;i*i<=n;i++) if(n%i==0) res += solve(n/i, i);

  return res;
}

class Refactoring {
public:
int refactor(int n) {
  return solve(n, 2) - 1;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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