Rating:
The flag is computed by a linear combination of gcd of cartesion products multipled by weighted sum of an encrypted array. Recognize that each position of array influences output linearly and independently. To find contribution of one idx in encrypted array, iterate through all possible GCD, 0 <= x <= N. For each GCD, iterate 0 <= k <= N, where k represents the number of positions x takes up. We can calculate possibilies of cartesion product based on this as f(k, x) = (N-k)^count(x) - f(k, factors of x for all factors) where count(x) is the number of values [0, N] whose gcd with x is x. The subtraction part of the equation can be memoized. This complexity is O(N^2 log(N)). See solve script.
