A - Sum equals LCM Editorial by evima
Let \(N\) be an integer at least \(2\).
[1] When \(N\) is a power of a prime number
Let \(N=p^e\ (1\leq e)\).
First, since \(2 \leq n\), it is necessary that \(A_i < N\). Also, \(N\) is the least common multiple of \(A_i\), so \(A_i\) must be a divisor of \(N\).
From the above considerations, \(A_i\) will be one of \(p^k\ (k < e)\), but these are divisors of \(p^{e-1}\), so the least common multiple will be at most \(p^{e-1}\).
Therefore, no \(A_1,A_2,\dots,A_n\) satisfy the conditions.
[2] When \(N\) is not a power of a prime number
When \(N\) is not a power of a prime number, \(N\) is an integer at least \(6\), with distinct prime factors \(p,q\ (p\neq q)\).
Here, let \(k=N-\frac{N}{p}-\frac{N}{q}\ (\geq N - \frac{N}{2} -\frac{N}{3} = \frac{N}{6} > 0)\), and the following satisfies the condition:
\((A_1,A_2,\dots,A_{k},A_{k+1},A_{k+2})=(\underbrace{1,1,\dots,1}_{k},\frac{N}{p},\frac{N}{q})\).
Why?
The conditions of \(2 \leq n\) and the sum being \(N\) are obviously satisfied.
Let’s consider whether the least common multiple of \(A_i\) is \(N\). The least common multiple of \(A_i\) is equal to that of \(\frac{N}{p}\) and \(\frac{N}{q}\).
The least common multiple of these two numbers is \(\frac{kN}{p}\) for the smallest \(k\) such that \(\frac{kN}{p}\) is a multiple of \(\frac{N}{q}\). \(\frac{kN}{p}\) will be a multiple of \(\frac{N}{q}\) when \(\frac{kq}{p}\) is an integer. Since \(p\) and \(q\) are distinct prime numbers, the smallest \(k\) for which this is an integer is \(p\).
Therefore, the least common multiple of \(\frac{N}{p}\) and \(\frac{N}{q}\) is \(N\), satisfying the conditions.
From the above considerations, it is sufficient to determine whether \(N\) is a power of a prime number, which can be done by factorizing \(N\) into prime factors.
The prime factorization of \(N\) can be obtained in \(O(\sqrt{N})\) time by trial division, which is sufficiently fast.
posted:
last update: