Anthony_Jakson's blog

A number theory problem !
By Anthony_Jakson, history, 4 years ago, In English

A problem came in my mind few days ago. And now I am very willing to know the ans. I tried but couldn't solve it.

You are given n numbers 1<= n <= (10^5) you have to maximize the gcd of those numbers.

You can do one operation : Replace a with a-1 (a is a number)

**Note: ** It is not a part of any ongoing contest.

Can any one please tell me any solution that will work in this time constraint. Thanks in advance.

I am very sorry guys. You have to maximize .. not minimize

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

Comments Comments (7)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

if all numbers are even or all numbers are odd then apply a — 1 in any a. Otherwise the GCD should be 1.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    [5, 10, 15], not all numbers are odd or even, gcd = 5.

    → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

If you can only change one item then you can calculate an array of your suffix and prefix.

and try to reduce each item by 1 then take the gcd(suffix[i + 1], prefix[i — 1], a[i] — 1).

If you can apply that operation for multiple items then i don't know how to solve that.

Also obviously sometimes you may not do that operation at all.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's just try to subtract 1 from each element one by one. If we get 1 as gcd we are good. Otherwise all other numbers are divisible by some prime number p, and such p is unique for each element we subtract 1 from. So we will get 1 in at most n * log (max a) operations (or we'll try all variants and will know answer if n is smaller)

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Anthony_Jakson (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Gcd of all numbers cannot be greater than smallest number , hence answer is smallest number or smallest number -1 , now you just have to check if u can achieve that, else gcd is 1.

→ Reply