Instantly share code, notes, and snippets.

# yuvipanda/Hint.md Created Oct 13, 2011

What would you like to do?
Card Shuffling Solution (InterviewStreet CodeSprint Fall 2011)

The main observation is that the card at index i (1 <= i <= N) ends up at index K * i % (N + 1) after 1 shuffle. So after x shuffles, the card will be at position K^x * i % (N + 1). We want to find the smallest x such that K^x * i = i for all i. In other words, we want K^x = 1. This is known as the multiplicative order of K mod (N + 1). Lagrange's theorem implies that this will be a factor of phi(N + 1) where phi is the Euler Totient function. So we can check all factors of phi(N + 1) and find the smallest one which works. See: http://en.wikipedia.org/wiki/Euler's_totient_function http://en.wikipedia.org/wiki/Lagrange's_theorem_(group_theory)

 #include #include #include #include #include using namespace std ; #define INF (int)1e9 #define MAXN 40000 int p,primes[10000],sieve[MAXN] ; void precompute() { for(int i = 2;i < MAXN;i++) if(!sieve[i]) { primes[p++] = i ; for(int j = i * i;j < MAXN;j += i) sieve[j] = 1 ; } } int getPhi(int N) { int phi = N ; for(int i = 0;primes[i] * primes[i] <= N;i++) if(N % primes[i] == 0) { while(N % primes[i] == 0) N /= primes[i] ; phi /= primes[i] ; phi *= primes[i] - 1 ; } if(N > 1) { phi /= N ; phi *= N - 1 ; } return phi ; } int MOD ; int power(int a,int b) { if(b == 0) return 1 ; int ret = power(a,b / 2) ; ret = 1LL * ret * ret % MOD ; if(b & 1) ret = 1LL * a * ret % MOD ; return ret ; } int ret,pr[30],ct[30],sz ; void solve2(int k,int r,int pow) { if(pow >= ret) return ; if(k == sz) { if(r == 1 && pow != 1) ret = pow ; return ; } for(int i = 0;i <= ct[k];i++) { solve2(k + 1,r,pow) ; r = power(r,pr[k]) ; pow *= pr[k] ; } } int solve2(int N,int K) { MOD = N + 1 ; int phi = getPhi(N + 1) ; sz = 0 ; for(int i = 0;primes[i] * primes[i] <= phi;i++) if(phi % primes[i] == 0) { pr[sz] = primes[i] ; ct[sz] = 0 ; while(phi % primes[i] == 0) phi /= primes[i],ct[sz]++ ; sz++ ; } if(phi > 1) { pr[sz] = phi ; ct[sz++] = 1 ; } ret = INF ; solve2(0,K,1) ; return ret ; } int main() { precompute() ; int runs ; scanf("%d",&runs) ; while(runs--) { int N,K ; scanf("%d%d",&N,&K) ; int ret = solve2(N,K) ; printf("%d\n",ret) ; } return 0 ; }