AshutoshChoudhary's blog

By AshutoshChoudhary, history, 2 months ago, In English

Q: Given an array of n integers, find the sum of value of GCD for all possible pairs.

2 <= n <= 10 ^ 5

1 <= a[i] <= 10 ^ 5

Tags gcd
»
2 months ago, # |
  Vote: I like it -7 Vote: I do not like it

u can use gcd convulation

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm unaware about that technique, can you please describe the algorithm ?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    or what we can do is count no.of pairs having (gcd=x) for every x from 1 to 1e5 using dp,now iterate over this x,so your answer is summation(x*(cnt)),this is standard question,ping me if you want implementation

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      please show the implementation

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it
        Spoiler
»
2 months ago, # |
  Vote: I like it +14 Vote: I do not like it

you can dp on number of pairs with gcd x, an then simply sum and multiply

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

you may look at submissions / Tutorial for this problem

it discus the same idea you talk about....