I am solving this problem but could not understand how to solve it efficiently.

Problem : you are given N numbers (a_i can be up to 10^6 and n can be up to 3*10^5). in one operation you can change a_i to a_i — 1 or a_i + 1 , find minimum operations to make gcd(a_1 , a_2 , . . . , a_n) > 1.

What I am thinking is , from i = 2 to max(a_i) for each number check how many operations are required to make gcd = i and print the minimum cost.

but the complexity of this approach is O(N*max(a_i)) which is resulting in TLE.

if you can only give hint I will try to learn and solve this problem.

thank you for your time.

https://codeforces.com/contest/850/problem/B I think this problem is a generalization of the one you are trying to sovle unless I misread somethinig(which I do pretty often)