Given N, find the smallest number A that A^A divisible by N

user_17871668 0
Viewed 104

This problem describes that :

Given N, find the smallest number A that A^A divisible by N. (N<=1.000.000.000)

E.g: N=9 , output A=3 (3^3 mod 9=0) ; given N=6 output A=6 (6^6 mod 6=0).

I calculate from 1 until I find number appropriate, but during I calculate variable (A^A) then data overflow. How can I find number A faster and no data overflow?

math algorithm
1 Answers
  1. The prime factors of A should be the same as the prime factors of N. Having less factors means A^A % N !=0, having more factors is pointless since we're looking for the smallest A.
  2. Let N have prime factorization 2^a * 3^b * 5^c .... The exponent array for N would be expo_N = [a,b,c...]
  3. Let y = product of prime factors of N. The exponent array for y would be [1,1,1...]. The exponent array of y^y will be expo_y = [y,y,y...].
  4. For y^y to be divisible by N, expo_y[i] >= expo_N[i] for i in range(length(expo_N)).
  5. Let x = max(a,b,c...). Now, using the points mentioned above, y >= x to satisfy point #4. If y>=x, you have the answer. Else, keep on multiplying y by 2 while y < x.

This approach doesn't involve actually exponentiating the numbers, so it would timeout or error out. Factorization of N can be done in O(sqrt(N)), the remaining operations will be done in O(logN) number of prime factors.

Example 1: N = 9
  1. expo_N = [3: 2] (since N = 3^2)
  2. y = 3, expo_y = [3: 3]
  3. Since expo_y[i] >= expo_N[i] for all i, answer is A = y = 3
Example 2: N = 6
  1. expo_N = [2: 1, 3: 1]
  2. y = 6, expo_y = [2: 6, 3: 6]
  3. Since expo_y[i] >= expo_N[i] for all i, answer is A = y = 6
Example 3: N = 384
  1. expo_N = [2: 7, 3: 1]
  2. y = 6, expo_y = [2: 6, 3: 6]
  3. expo_N[2] = 7, so we multiply y by 2
  4. y = 2*y = 12, expo_y = [2: 24, 3: 12]
  5. Now the condition is satisfied, so the answer is A = y = 12
user_93507200
Related