Created

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist

Card Shuffling Solution (InterviewStreet CodeSprint Fall 2011)

View 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)

View Hint.md
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 ;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.