Shuffle puzzle problem

Next tag has an interesting card puzzle:

Given a deck of nCards unique cards, cut the deck iCut cards from top and perform a perfect shuffle. A perfect shuffle begins by putting down the bottom card from the top portion of the deck followed by the bottom card from the bottom portion of the deck followed by the next card from the top portion, etc., alternating cards until one portion is used up. The remaining cards go on top. The problem is to find the number of perfect shuffles required to return the deck to its original order. Your function should be declared as:

static long shuffles(int nCards,int iCut);

Please send the result of shuffles(1002,101) along with your program and your resume to 'resume' at nextag.com.

This is an interesting problem and working out a solution for small number should be straight forward for a lot of people but it won't scale. You have to think of the principle behind it to come up with a good algorithm that can solve it in seconds, or even better, milliseconds. Below is my reference implementation:

package com.hongbing;

import java.util.Date;

public class BetterShuffle {

  static long shuffle(int nCards, int iCut) {
    int perfectShuffle[] = new int[nCards];
    
    int i = iCut - 1;
    int j = nCards - 1;
    int k = nCards - 1;
    while (i >= 0 && j >= iCut) {
      perfectShuffle[k--] = i--;
      perfectShuffle[k--] = j--;
    }
    
    while (i >= 0) {
      perfectShuffle[k--] = i--;
    }
    
    while (j >= iCut) {
      perfectShuffle[k--] = j--; 
    }

    long count = 0;
    for (i = 0; i < nCards; i++) {
        long cardShuffleCount = 1;
        int current = perfectShuffle[i];
        while (perfectShuffle[current] != i) {
          cardShuffleCount++;
          current = perfectShuffle[current];
        }
        cardShuffleCount++;
        
        if (count == 0) {
          count = cardShuffleCount;
        }
        else {
          count = lcm(cardShuffleCount, count);
        }
    }
    
    return count;
  }

  private static long lcm(long n, long m) {
    return n * m / gcd(n, m);
  }

  private static long gcd(long n, long m) {
    if (m == 0) {
      return n;
    }
    
    long remainder = n % m;
    return gcd(m, remainder);
  }


  /**
   * @param args
   */
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    Date start = new Date();
    System.out.println("Shuffle count : " + BetterShuffle.shuffle(1002, 101));
    //System.out.println("Shuffle count : " + BetterShuffle.shuffle(10, 3));
    Date end = new Date();
    
    System.out.println("Number of seconds : " + (end.getTime() - start.getTime()) / 1000);
  }
}