virtual100's blog

By virtual100, history, 3 weeks ago, In English,

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.

  • Vote: I like it
  • +4
  • Vote: I do not like it

3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it I think this problem is a generalization of the one you are trying to sovle unless I misread somethinig(which I do pretty often)