P2755 Shuffling Problem

There are $ 2n $ cards, numbered as $$ 1,2,3 \dots n,n+1, \dots 2n $$ which is also the initial order of the deck. One shuffle transforms the sequence into $$ n+1,1,n+2,2,n+3,3,n+4,4 \dots 2n,n $$. It can be proven that for any natural number $ n $, there exists a smallest positive integer $ m $ such that after performing the shuffle $ m $ times, the deck returns to its initial order for the first time. Given $ n $ ($ n \le 10^8 $), compute this $ m $.

One line containing a positive integer $ n $.

One line containing a positive integer $ m $.

For $ 100\% $ of the testdata, $ 1 \le n \le 10^8 $. Translated by ChatGPT 5