SPOJ：カードシャッフル

Question

最近私はオンラインジャッジの質問を解決し始めました。 Iは、this question in SPOJで立ち往生しています：ここ

はNカードをシャッフルするためのアルゴリズムである：

1. カードは、KがN
2. の係数であるK等しい杭、ボトムNに分割され/ Kカードは同じ順番でパイル1に属します（最初のパイルのボトムカードはパイル1のボトムカードです）。
3. 下のN/Kカードはパイル2に属します。
4. シャッフルされたパイルの一番上のカードがパイル1の一番上のカードです。次のカードはパイル2の一番上のカードです。シャッフルされたパイルのKthカードはパイルKの一番上のカードです。 （K + 1）番目のカードは現在パイル1の最上部にあるカードであり、（K + 2）番目はパイル2の最上部にあるカードなどである。

たとえば、N = 6でK = 3の場合、シャッフルされたカードABCDEF（上から下）のデッキは「ECAFDB」に変更されます。

NとKを指定すると、パイルが元の順序に復元されるまでに必要な最小シャッフル数はどれくらいですか？

---

私がシミュレートしようとしたが、それは時間制限を超えています。何か数学的方程式はありますか？

Answer 1

はい、この問題のための数学的な解決策があります。

まず、このような問題にアプローチする方法のヒントを紹介してから、実際の解決策に関するヒントをいくつか紹介します。まだ挑戦が残っているように、私はそれを完全に終わらせません。

だから：どのようにこのような問題にアプローチするのですか？あなたがしたことは、実際には良いスタートです。いくつかの小さなケースに対してシミュレーションを作成して実行します。シミュレーションはかなり速くなければなりません。今、いくつかの価値があります。紙の上にそれらを書き留めて、それらを見つめ始める。 K = x とN = y の場合、結果はz と多くのペアがあります。数式を計算してみてください。 x、yまたはzの固定値を持つトリプルに注目してください。彼らの共通点は何がありますか？等々。あなたは凝視して、しばらくすると明るいアイデアを得ます:)

Now：この特定の問題に関するいくつかのヒント。シャッフルを1回繰り返し、各カードがどこに行くかをメモします。例えば、カード1はポジション3に、カード3はポジション2に、というように続きます。いくつかの鎖がこのように形成されることに注意してください。例えば、n = 6、k = 3の例では、長さが6：1→3→2→6→4→5→1 。次に、すべてのチェーンの長さを計算し（各カードはちょうど1つのチェーンに属します）、答えがこれらの長さにどのように依存するかを調べます。

これで問題を解決するのに十分です。

EDIT：1回の反復をシミュレートする制約を見ると、非常に遅い場合があります。その場合、2番目のヒントでアドバイスをした後、実際にシャッフルをシミュレートすることなくチェーンの長さを計算してみる