TopCoder problem "UGroupOrder" used in TCI '02 Round 1 A (Division I Level Two)



Problem Statement

    Two integers are relatively prime if they have no common factors other than 1. For example, 8 and 6 are not relatively prime since they are both divisible by 2. 27 and 10 are relatively prime since they have no common factors other than 1. Note that 1 is relatively prime to all numbers.



The Nth U-group is a special group of integers denoted U(N). An integer B is in U(N) if:

1) 0 < B < N

2) B is relatively prime to N



All arithmetic done in U(N) is performed modulo N. This means:

If C and D are in U(N) then: C*D means (C*D) mod N



The order of an element K in a U-group U(N) is the smallest positive integer E such that:

(K^E) mod N = 1

where ^ denotes exponentiation

In other words, how ever many times you have to multiply K times itself mod N to get 1. In a U-group, every element will have a finite order.



Given N you are going to return the order of each element in U-group U(N).

For example:

N = 8

U(N) = {1,3,5,7}

Orders = {1,2,2,2} since

(1^1) mod 8 = 1 mod 8 = 1

(3^2) mod 8 = (3*3) mod 8 = 9 mod 8 = 1

(5^2) mod 8 = (5*5) mod 8 = 25 mod 8 = 1

(7^2) mod 8 = (7*7) mod 8 = 49 mod 8 = 1

See examples for further clarification.



Create a class UGroupOrder that contains the method findOrders, which takes an int N and returns a int[] containing the order of each corresponding element in U(N).
 

Definition

    
Class:UGroupOrder
Method:findOrders
Parameters:int
Returns:int[]
Method signature:int[] findOrders(int N)
(be sure your method is public)
    
 

Notes

-The index of each returned element corresponds to the elements of U(N). The first element of U(N) corresponds to the first element in the return value. The second element of U(N) corresponds to the second element in the returned value ...
-Note that (a*b) mod N = ((a mod N)*(b mod N)) mod N
 

Constraints

-N will be between 2 and 51 inclusive
 

Examples

0)
    
9
Returns: { 1,
  6,
  3,
  6,
  3,
  2 }
1^1 mod 9 = 1

2^6 mod 9 = 1

4^3 mod 9 = 1

5^6 mod 9 = 1

7^3 mod 9 = 1

8^2 mod 9 = 1
1)
    
8
Returns: { 1,
  2,
  2,
  2 }
This is the example given in the problem statement.
2)
    
15
Returns: { 1,
  4,
  2,
  4,
  4,
  2,
  4,
  2 }
3)
    
51
Returns: 
{ 1,
  8,
  4,
  16,
  16,
  8,
  16,
  16,
  4,
  16,
  2,
  8,
  16,
  16,
  16,
  8,
  8,
  16,
  16,
  16,
  8,
  2,
  16,
  4,
  16,
  16,
  8,
  16,
  16,
  4,
  8,
  2 }
4)
    
10
Returns: { 1,
  4,
  4,
  2 }
5)
    
2
Returns: { 1 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=903

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4324&pm=903

Writer:

brett1479

Testers:

alexcchan , lbackstrom

Problem categories:

Advanced Math