Joseph's Problem(0)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2800
毎度毎度悩ませてくれるジョセフさん。今度は、入力N,Kに対して、
を計算するというだけの問題ですが、やはりそのままの計算ではTLEになります。この手の問題は、単純に定義式通りで解を出力するコードをまず書いて、さらに小さな入力に対して計算過程を列挙するような処理を付け加える作業を行っておくと考えやすい。色々なN,Kの組み合わせで計算過程を調べていくと、規則性が見つかるはずです。
��1<=i<=n(k mod i)
規則性の問題は今までいくつか取り組んできましたが、これもなかなか面白い。一見、規則性があるようなないような・・・という数列を、最終的に一つの数式でまとめてしまう過程を是非楽しんでください。当然、私のコードも公開するつもりですが、とりあえずは頭の体操として、皆さん楽しんでください。
私も137Bまで短縮しましたが、まだまだ改善の余地がありそうな感触です。規則性マニアの方々の、シュゴー(゜Д゜)なアイデア待ってます。