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.000Memory 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
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
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 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 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 { // Sieve of Erathostenes to find all the necessary prime numbers: vector vector 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; }
发表评论