Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM599 DIV1 EASY - BigFatInteger (この記事を編集する[管理者用])

Source

TopCoder SRM599 DIV1 EASY (250pt)
Problem Statement

問題概要

$X=1$ から初めて毎ターン以下のどちらか操作を行う.
 素数 $p$ を $X$ にかける
 $X$ の約数を $X$ にかける
$X=A^B$ となるまでの最小ターン数を求める問題.
$2 \leq A \leq 10^6$
$1 \leq B \leq 10^6$

解法

まず,$A$ の素因数は全部操作1で加えておく.
後は,それぞれの素因数は毎回倍々にできる(端数は適当に調整できる)ので,操作2の回数は最も多い素因数に依存する.
操作1の回数,操作2の回数は愚直に調べれば良い.

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

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int get_cnt(int n){
  int res = 0;
  while(n > 1){
    res++;
    n = (n+1)/2;
  }
  return res;
}

class BigFatInteger {
public:
int minOperations(int A, int B) {
  int i, j, k;
  int arr[1000], arr_size = 0;
  int res;

  for(i=2;i<1000000;i++){
    if(A%i==0){
      arr[arr_size] = 0;
      while(A%i==0) arr[arr_size] += B, A/=i;
      arr_size++;
    }
  }

  res = 0;
  rep(i,arr_size) res = max(res, get_cnt(arr[i]));
  res += arr_size;

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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