aboutsummaryrefslogtreecommitdiff
path: root/maximise_num_div.c
blob: 66ecab34633744636ab1af10165a80621bdddd84 (plain)
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
// 1808. Maximize Number of Nice Divisors
#include <stdio.h>

/*
 * you are given a positive integer 'prime_factors'. you are asked to construct
 * a positive integer 'n' that satisfies the following conditions.
 * - the number of prime factors of 'n' (not necessarily distinct) is at most
 * 'prime_factors'
 * - the number of nice divisors of 'n' is maximised. note that a divisor of 'n'
 * nice if it is divisible by every prime factor of 'n'. for example if 'n =
 * 12', then its prime factors are '[2,2,3]', then '6' and '12' are nice
 * divisors, while '3' and '4' are not. return the number of nice divisors of
 * 'n'. since that number can be too large, return it modulo 10e9+7. note that a
 * prime number is a natural number greater than 1 that is not a product of two
 * smaller natural numbers. the prime factors of a number 'n' is a list of prime
 * numbers such that their product equals 'n'
 */

long modpow(long base, int exp, int mod) {
  long res = 1;
  for (; exp; exp >>= 1) {
    res *= (exp & 1 ? base : 1) % mod;
    base *= (base % mod);
  }
  return res;
}

int maxNiceDivisors(int prime_factors) {
  int st[6] = {1, 2, 3, 4, 5, 6}, mod = 1e9 + 7;
  return prime_factors < 6 ? st[prime_factors]
                           : st[3 + prime_factors % 3] *
                                 modpow(3, prime_factors / 3 - 1, mod) % mod;
}

int main() {
  printf("%d\n", maxNiceDivisors(5)); // expect: 6
  printf("%d\n", maxNiceDivisors(8)); // expect: 18
}