Power, Binary Exponentiation

Leetcode 1808. Maximize Number of Nice Divisors

This is the last question of the Leetcode weekly contest of Mar 27, 2021. It is not that hard if you have solved the problem of LC 50 POW(x, n) before.

1808. Maximize Number of Nice Divisors

From the example, we can guess, if we can split the number of prime factor as following:

• 5: {2, 2, 2} {3, 3}. First group has 3 number and the second group has 2 number. The answerw is 3X2
• 6: {2, 2, 2} {3, 3, 3}. First group has 3 number and the second group has 3 number. The answerw is 3X3
• 7: {2, 2, 2} {3, 3, 3, 3}. First group has 3 number and the second group has 3 number. The answerw is 3X4 = 3*2*2, as 4 = 2X2, we can also get this one {2,2,2}, {3,3}, {5, 5}
• 8: {2, 2, 2} {3, 3, 3}{5,5}. First group has 3 number and the second group has 3 number. The answerw is 3*3*2
• 9: {2, 2, 2} {3, 3, 3}{5,5, 5}. First group has 3 number and the second group has 3 number, same for the third group. The answer is 3*3*3

We can guess that the maximum value can be get in the format of 3^m * 2^n.

You can prove this by induction. Here I did not give the proof. Maybe later, I will show the proof.

Then the problem will be simple

if (n%3==0) return pow(3, k) where k = n/3
if (n%3==1) return 4*pow(3, k) where k = (n-4)/3
if (n%3==2) return 2*pow(3, k) where k = (n-2)/3

For the pow function, we should use a faster one with the complexity of O(log n), or we will get TLE. For the faster Algo, see this post.

Real code

const int mod = 1e9 + 7;
long long binpow(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = (res * a) % mod; 
      a = (a * a) % mod;
    b >>= 1;
  }
  return res%mod;
}
class Solution {
public:
    int maxNiceDivisors(int n) {
        if (n<3) return n;
        if (n%3 == 0) {auto k = n/3; return binpow(3, k);} 
        if (n%3 == 1) {auto k = (n-4)/3; return 4*binpow(3, k)%mod;} 
        if (n%3 == 2) {auto k = (n-2)/3; return 2*binpow(3, k)%mod;} 
        return 0;
    }
};

Reference

[1]https://jimmy-shen.medium.com/power-binary-exponentiation-and-matrix-exponentiation-f84d93a23841

[2]https://oi-wiki.org/math/quick-pow/