10710 - Chinese Shuffle

[muvee]

My evidently pathetic algorithm that takes about 5 seconds on certain cases is as follows :

Let the input number be N

1) If N is odd , N=N+1
2) Set x = 2 and counter=1
While(x!=1)
{
x = (x<<1)%(n-1)
counter++
}




This is based on the observation that if you label the cards from 0 to n-1, then every card moves from k to (2*k)mod(n-1)

Firstly, is my observation correct that the number of shuffles required is equal to the number of shuffles it takes for card number 2 (having index 1 in using the labelling system I described) to return to index 1.

And if yes, since my algorithm is too slow, any hints are more than welcome!
[/code]

[Abednego]

I love this problem, Little Joey! It really shows you that you should think first before writing code. I submitted the Rabin-Miller test first without even thinking that numbers other than primes could be Jimmy-numbers. Of course, it turns out that the problem is much easier than primality testing. :-)

[Destination Goa]

My solution checks that 2^(N-1) == 1 modulo N (same thoughts about repositioning gave me this fact). I think yours does the same, but it performs O(N) operations to find that power. You should use O(log(N)) algorithm to find 2^(N-1).

[Eduard]

Hello muvee
For Log(N) solution you can first solve problem 374(Big Mod).

[Vexorian]

Anyone may assist me solving the WA with some I/O samples I might be missing?

PS: I did notice it doesn't work only on primes.