Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM394 DIV2 HARD - ProperDivisors (この記事を編集する[管理者用])

Source

TopCoder SRM394 DIV2 HARD (1000pt)
Problem Statement

問題概要

d(m)でmのcoolな約数の数を表す.
coolな約数xとは,xは1以上m未満で,xはmを割り切り,x^nはmを割り切れないもの.
 d(a)+d(a+1)+…d(a+b)
を求める問題.
aは10^6以下,bは10^7以下,nは2以上10以下.

解法

Σの順番を入れ替える.結局答えはだいたい
 a~a+bまでの中の2の倍数の数(2を除く) + a~a+bまでの中の3の倍数の数(3を除く) + …
 - a~a+bまでの中の2^nの倍数の数 - a~a+bまでの中の3^nの倍数の数 + …
みたいな感じになる.

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

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

class ProperDivisors {
public:
int analyzeInterval(int a, int b, int n) {
  int i,j,k;
  int res = 0;

  REP(i,2,a+b+1){
    res += (a+b)/i - (a-1)/i;
    if(i>=a) res--;
  }

  for(i=2;;i++){
    k=1; rep(j,n) k*=i;
    if(k>a+b) break;

    res -= (a+b)/k - (a-1)/k;
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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