Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SPOJ 3107 - Odd Numbers of Divisors [ODDDIV] (この記事を編集する[管理者用])

Source

Al-Khawarizm 2008
SPOJ 3107 [ODDDIV]

問題概要

約数の個数がちょうどK個であるような区間[low,high]に入ってる整数の数を求める問題.
Kは奇数,lowとhighは10^10以下.
テストケースの数は最大で10万.

解法

約数の個数が奇数なので平方数のみ考えれば良い.
最初に,10^5個の平方数に対して,約数の個数を全部求めておいて,約数の個数がm個であるような平方数のリストを作っておく.
後は,テストケースごとに,2分探索して,範囲[low,high]に含まれるものの数を求める.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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