Card Shuffling Solution (InterviewStreet CodeSprint Fall 2011)

Hint.md

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)

problemsetter.cpp

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<vector>
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 ;
}