##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
| # | Title | Points | Solved | Admin | |
|---|---|---|---|---|---|
The prefix GCD sequence is non-increasing, and each time it changes, the new value must be a strict divisor of the previous one. This implies that the sequence of distinct values forms a chain of length : where .
For a fixed current GCD , if we append a new element , the GCD remains if is a multiple of , which gives valid choices. If the GCD changes to a strict divisor ( and ), must satisfy . The number of such choices is exactly by Möbius inversion.
We can view this process as traversing a DAG where nodes are integers from to . Each node has a self-loop with weight , and there is a directed edge from to with weight . We want to find the sum of weights of all paths of length that traverse exactly non-loop edges.
Since is up to , we can compute the generating function for paths of length . The contribution of staying at node is . For a specific chain , the generating function is . We need to extract the coefficient of from this rational function.
Notice a beautiful property: for any strict descent and , we have , which implies . Thus, along any valid path, the self-loop weights are strictly increasing and therefore distinct. This guarantees that all poles in the denominator are distinct, and we can maintain the rational function using partial fraction decomposition dynamically on the DAG.
Let be the rational function for paths ending at with exactly distinct values. We can represent where iterates over ancestors of . When transitioning from to , we multiply the current function by . For each existing pole , we use the identity:
Because , the denominator is never zero. We can dynamically push these partial fraction coefficients level by level. A state stores the coefficient of for paths ending at . Since must be a multiple of , we only need an array of size for each , requiring minimal memory.
To optimize the transition, we first precompute all valid edges in time using the divisor sieve. During the DP step (running times), for each destination , we accumulate the incoming coefficients into a temporary array and then split them using the partial fraction formula in time. The total DP takes operations.
Finally, for each and its valid poles , we add to the answer. The overall time complexity is extremely fast and comfortably passes within the generous time limit.