Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM523 DIV1 EASY/DIV2 MEDIUM - CountingSeries (この記事を編集する[管理者用])

Source

TopCoder SRM523 DIV1 EASY (250pt)
TopCoder SRM523 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

初項a,公差bの等差数列と,初項c,公比dの等比数列を考える.
少なくても片方に含まれる,upperBound以下の整数はいくつあるかを求める問題.
a, b, c, upperBoundは1以上10^12以下.dは10^5以下.

解法

色々場合分けが出てくるので,しっかり確かめながらやる.
等差数列に対しては,割り算で項の数がわかって,等比数列に対しては,upperBoundを超えないものを列挙して,それが等差数列に含まれないなら数える.

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

#define ll long long

int is_include(ll a, ll b, ll c){
  if(c < a) return 0;
  if( (c-a)%b==0 ) return 1;
  return 0;
}

class CountingSeries {
public:
ll countThem(ll a, ll b, ll c, ll d, ll upperBound) {
  ll res;

  res = (upperBound - a) / b + 1;
  if(upperBound < a) res = 0;

  if(d==1){
    if(c <= upperBound) res += 1 - is_include(a, b, c);
  } else {
    while(c <= upperBound){
      res += 1 - is_include(a, b, c);
      c *= d;
    }
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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