public
Created

Card Shuffling Solution (InterviewStreet CodeSprint Fall 2011)

  • Download Gist
Hint.md
Markdown

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
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
#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 ;
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.