Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM473 DIV2 HARD (1000pt)
Problem Statement

問題概要

D(X)でXの各桁の和を表すとする.
X, Yは整数で,Y = X / D(X)なるとき,YはXの親ということにする.
区間[A, B]の中に,子供のいない数は幾つあるかを求める問題.
A,Bは10億以下で,区間内の数字の数は10001以下.

解法

1個ずつ子どもがいないかどうか判定する.
Yの子供の候補は,X = Y * D(X)より,Yの倍数のみ調べればよくて,さらにD(X)は大きくないので,100倍ぐらいまで調べれば良い.

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

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

#define ll long long

int D(ll X){
  int res=0;
  while(X) res += X%10, X/=10;
  return res;
}

int solve(ll Y){
  int i; ll X=Y, d;
  rep(i,150){
    X += Y;
    d = D(X);
    if(X == Y*d) return 0;
  }
  return 1;
}

class ChildlessNumbers {
public:
int howMany(int A, int B) {
  int res=0;
  while(A<=B) res += solve(A), A++;
  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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