Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

PKU 3741 - Number System Converter (この記事を編集する[管理者用])

Source

POJ Monthly Contest - 2009.08.23
PKU 3741

問題概要

文字列をP進数と思って整数に直して,その整数をQ進数と思って文字列に直す.
P進数に直すとき,ある桁の数がPを超えていても気にしない.
最初の文字列が与えられたとき,この操作を繰り返すと,何に収束するかを答える問題.
P < Q,最初の文字列は5000000文字以下.

解法

収束先はqより小さい1桁の数.
1ステップで,
 Q → P, Q^k → P^k
などに変わることから推測すると,
最初から,Qより小さいならそのまま,そうでないなら,(入力をQ進数とみなして) Qより小さくなるまでQ-Pを引くと良い.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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