LCM is Legendary Counting Master

The whole scary-looking lcm sum is a trap. If you try to store partial sums of reciprocals, congrats, you have volunteered for fraction hell. The intended move is to prove the sum can never exceed $1$, then characterize exactly when it hits $1$.

Key Inequality

Take two positive integers $x<y$ and let $g=\gcd(x,y)$. Then

$\frac{1}{\operatorname{lcm}(x,y)}=\frac{g}{xy}.$

Also,

$\frac1x-\frac1y=\frac{y-x}{xy}.$

Since $g=\gcd(x,y)$ divides $y-x$, and $y-x>0$, we get $g\le y-x$. Therefore

$\frac{1}{\operatorname{lcm}(x,y)}\le \frac1x-\frac1y.$

Equality happens exactly when

$\gcd(x,y)=y-x.$

That equality condition is the whole damn problem.

Bounding The Whole Sum

Let the final strictly increasing sequence be $a_1<a_2<\cdots<a_n$. Define

$S=\sum_{i=1}^{n-1}\frac1{\operatorname{lcm}(a_i,a_{i+1})}+\frac1{\operatorname{lcm}(a_n,a_1)}.$

For the first edge,

$\frac1{\operatorname{lcm}(a_1,a_2)}\le \frac1{a_2},$

because the lcm is a multiple of $a_2$.

For the last cyclic edge,

$\frac1{\operatorname{lcm}(a_n,a_1)}\le \frac1{a_n},$

because the lcm is a multiple of $a_n$.

For every middle edge $i=2,3,\ldots,n-1$, use the inequality from above:

$\frac1{\operatorname{lcm}(a_i,a_{i+1})}\le \frac1{a_i}-\frac1{a_{i+1}}.$

Now telescope:

$S\le \frac1{a_2}+\sum_{i=2}^{n-1}\left(\frac1{a_i}-\frac1{a_{i+1}}\right)+\frac1{a_n}.$

The middle sum becomes $\frac1{a_2}-\frac1{a_n}$, so

$S\le \frac1{a_2}+\left(\frac1{a_2}-\frac1{a_n}\right)+\frac1{a_n}=\frac2{a_2}.$

Since the sequence is strictly increasing and positive, $a_2\ge 2$. Thus

$S\le 1.$

But the problem asks for $S\ge 1$. So actually we need $S=1$, and every inequality used above must be equality. No wiggle room. Math put the sequence in handcuffs.

Forced Prefix

For $S=1$, we need $\frac2{a_2}=1$, so

$a_2=2.$

Since $a_1<a_2$ and values are positive, this forces

$a_1=1.$

So if position $1$ is fixed to something other than $1$, or position $2$ is fixed to something other than $2$, the answer is immediately $0$.

For $n=2$, this already fully solves the condition: only $[1,2]$ works.

Middle Transitions

For every edge after $a_2$, equality must hold:

$\frac1{\operatorname{lcm}(a_i,a_{i+1})}=\frac1{a_i}-\frac1{a_{i+1}}.$

As proven earlier, for $x<y$ this means

$\gcd(x,y)=y-x.$

Let $d=y-x$. Then

$\gcd(x,y)=\gcd(x,x+d)=\gcd(x,d).$

So the condition becomes

$\gcd(x,d)=d,$

which is equivalent to

$d\mid x.$

Therefore a valid transition is exactly:

$x\to x+d\quad\text{where }d\mid x.$

That is beautifully simple: after the forced prefix $1,2$, each next value is obtained by adding a divisor of the current value.

Counting With DP

Build a directed graph on values $1,2,\ldots,m$. For every value $x$, add edges

$x\to x+d$

for every divisor $d$ of $x$ such that $x+d\le m$.

Then count paths of length $n-2$ starting from value $2$, while respecting fixed positions.

Let $dp[x]$ be the number of ways for the current position to have value $x$.

Initialization:

$dp[2]=1.$

Then for positions $3$ through $n$, transition along graph edges. If the current input position is fixed to value $v$, only transitions ending at $v$ are allowed. If it is zero, any endpoint is allowed.

At the end, sum all $dp[x]$.

Correctness Proof

We prove the algorithm counts exactly the valid completions.

First, for any valid strictly increasing sequence, the lcm sum satisfies $S\le 2/a_2\le 1$. Since the problem requires $S\ge 1$, any good sequence must have $S=1$. Therefore $a_2=2$, and hence $a_1=1$.

Second, equality in the bound requires equality on every middle edge $(a_i,a_{i+1})$ for $i\ge 2$. For an edge $x<y$, equality is equivalent to $\gcd(x,y)=y-x$, which is equivalent to $y=x+d$ for some divisor $d$ of $x$. Thus every good sequence corresponds to a path in our graph starting from $2$.

Third, any path in this graph starting from $2$, combined with forced prefix $a_1=1$, satisfies all equality conditions. Its sum is

$\frac12+\sum_{i=2}^{n-1}\left(\frac1{a_i}-\frac1{a_{i+1}}\right)+\frac1{a_n}=\frac12+\left(\frac12-\frac1{a_n}\right)+\frac1{a_n}=1.$

So every counted path gives a good sequence.

Finally, the DP respects every fixed nonzero position and allows every zero position to be chosen freely among valid graph transitions. Therefore it counts exactly the required replacements.

Complexity

For each test case, the graph has

$\sum_{x=1}^m \tau(x)=O(m\log m)$

edges. The DP runs over positions and edges, so the time is

$O(nm\log m)$

in the usual divisor-counting sense, easily fine for $m\le 3000$ and total $m\le 3000$.

Memory is $O(m+m\log m)$.