最小公倍数 SRM 661 Div1 250: MissingLCM

时间:2022-04-23 15:34:44

Problem Statement

The least common multiple (denoted "lcm") of a non-empty sequence of positive integers is the smallest positive integer that is divisible by each of them. For example, lcm(2)=2, lcm(4,6)=12, and lcm(1,2,3,4,5)=60.

Alice had a positive integer N. Then she chose some positive integer M that was strictly greater than N. Afterwards, she computed two values:

the value A = lcm(N+1, N+2,
..., M) and the value B = lcm(1, 2, ..., M). She was surprised when she saw that A = B.the value A = lcm(N+1, N+2,
..., M) and the value B = lcm(1, 2, ..., M). She was surprised when she saw that A = B.the value A = lcm(N+1, N+2,
..., M) and the value B = lcm(1, 2, ..., M). She was surprised when she saw that A = B.the value A = lcm(N+1, N+2,
..., M) and the value B = lcm(1, 2, ..., M). She was surprised when she saw that A = B.the value A = lcm(N+1, N+2,
..., M) and the value B = lcm(1, 2, ..., M).

You are given the int N. Find and return the smallest M Alice could have chosen. (Such an M will always exist.)

Definition

  • ClassMissingLCM
  • MethodgetMin
  • Parametersint
  • Returnsint
  • Method signatureint getMin(int N)
(be sure your method is public)

Limits

  • Time limit (s)2.000
  • Memory limit (MB)256

Constraints

  • N will be between 1 and 1,000,000, inclusive.

Test cases

    • N1

    Returns2

    Alice needs to choose an M > 1 such that lcm(2,...,M) = lcm(1,...,M). We can see M=2 is the minimum value that works, since lcm(1,2) = lcm(2) = 2.
    • N2

    Returns4

    • N3

    Returns6

    We have lcm(4,5,6) = lcm(1,2,3,4,5,6) = 60.
    • N4

    Returns8

    • N5

    Returns10

    • N42

    Returns82

    Oh... that doesn't fit the pattern.
      • N999999

      Returns1999966

    +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

  1. In this problem the actual LCM values used can be notably large. It is best to avoid approaches that calculate them directly. Then how about we think of this problem in terms of the prime factorization of the numbers. For example, consider two numbers: 12 and
    135. Their prime factorizations are: 22⋅3 and 33⋅5.
    The prime factorization of the LCM will be: 22⋅33⋅5.
    In other words, for each prime number , we take the maximum exponent of the prime number among the two numbers we are calculating the LCM for. How does this translate to the two LCMs used?

    A=LCM(N+1,N+2,...,M) 

    B=LCM(1,2,...,M) 

    A=B

    We need to translate this into distinct conditions, one for each relevant prime number:

    a=max(ep(N+1),ep(N+2),...,ep(M)) 

    b=max(ep(1),ep(2),...,ep(M)) 

    a=b

    Where ep(x) is
    the exponent of prime number p in
    the prime factorization of x,
    the maximum number of times you can repeatedly divide x by p.
    In words we just want the maximum exponent of prime p among
    all the factorizations between N+1 and M and
    between 1 and M to
    be equal. Try this:

    b=max(ep(1),ep(2),...,ep(N),ep(N+1),...,ep(M)) 

    b=max(ep(1),ep(2),...,ep(N),max(ep(N+1),...,ep(M))) 

    b=max(ep(1),ep(2),...,ep(N),a)

    What happens here is we take advantage that the maximum operation is associative. This means max(a,b,c)=max(a,max(b,c))=max(max(a,b),c).
    The useful thing to conclude about this: b≥a.
    There's more:

    b=max(max(ep(1),ep(2),...,ep(N)),a) 

    c=max(ep(1),ep(2),...,ep(N)) 

    b=max(c,a)

    We want a=b=max(c,a):
    This means we want c≤a.
    Note that c is
    constant, as it's determined by the numbers between 1 and N.
    So we just need to look for a value of M such
    that the maximum exponent of p among N+1,N+2,...M is
    greater than or equal to c.

    There must be a number x>N for
    which ep(x)≥c,
    this means that the exponent of p in
    the prime factorization of x.
    If we take the maximumep(i) for
    all i between N+1,...,M,
    the result would be at least c,
    meaning that using M=x would
    be correct. M=x+1 and
    any Mgreater
    than x would
    also be correct. If we find the minimum M that
    is valid for p,
    then we can assume that all greater numbers will also be valid for p.
    This minimum M will
    be the smallest x>N for
    which ep(x)≥c.

    Did you notice that in the examples it initially appears that the result is always 2N and
    then the result seems to be smaller than 2N but
    not far apart?

    There is a good explanation for this. c is
    the maximum exponent of p for
    some number less than or equal to N,
    let's call that number m. 2m will
    also have that exponent for p (unless p=2,
    in which it will have an even larger exponent). Making 2m a
    valid value for M.
    If we pick M=2N,
    we will guarantee that this happens for all relevant prime numbers. This is useful because it means we only need to search for xamong
    numbers less than or equal to 2N.

    For each prime p,
    there will be a distinct minimum valid M ,
    we should pick the maximum out of all of them. This number will be valid for all primes we try. Note that when p>N,
    any M>N will
    be correct. Because when p>N , c is
    zero, none of the numbers smaller than or equal to N will
    be multiples of p,
    so the maximum exponent will be 0. This means we only need to repeat this for all the prime numbers that are less than or equal to N.

    For each prime number we need to find c and
    also find the minimum x such
    that: ep(x)>c and N<x≤2N.
    The final improvement we need is to notice that given p,
    we only need to think in terms of numbers that are multiples of p.
    For i≤N,
    only values of i that
    are multiples of pwill
    have an exponent of p in
    their prime factor, so only they are relevant for the calculation of c.
    For i>N,
    only multiples of p may
    have an exponent larger than or equal to c.
    In total we will try all the multiples of p less
    than or equal to 2N.
    This is repeated for each p<N.
    The final number of steps needed is: 2N2+2N3+2N5+...+2NP where P is
    the maximum prime that doesn't exceed N.
    This number of steps is very good and the complexity would be similar to the Sieve of Eratosthenes'. A simple way to tell that complexity is O(NN−−√) :
    For all P>2N−−−√, 2NP=1.
    There are 2N−2N−−−√ such
    values, this is O(N).
    For the other O(N−−√) values
    of p,
    even if we assumed O(N) steps,
    the total complexity would still be: O(N+NN−−√).
    We are ready to implement this solution:

    vector<int> get_primes(int N)
    {
    // Sieve of Erathostenes to find all the necessary prime numbers:
    vector<int> res;
    vector<bool> composite(N + 1, false); for (int p = 2; p <= N; p++) {
    if (! composite[p]) {
    for (int i = p+p; i <= N; i += p) {
    composite[i] = true;
    }
    res.push_back(p);
    }
    }
    return res; } int get_exponent(int x, int p)
    {
    int r = 0;
    while (x % p == 0) {
    r++;
    x /= p;
    }
    return r;
    } int getMin(int N)
    {
    int res = 2;
    // For each prime number <= N:
    for (int p: get_primes(N) ) {
    // first find the maximum exponent of p among numbers <= N
    // (in the explanation , this max_exp is c)
    int max_exp = 0;
    int i = p;
    while (i <= N) {
    max_exp = std::max(max_exp, get_exponent(i,p) );
    i += p;
    }
    // seek the minimum i such that get_exponent(i,p) >= max_exp:
    while (get_exponent(i,p) < max_exp) {
    i += p;
    }
    // the maximum for all ps is the result:
    res = std::max(res, i);
    }
    return res;
    }