AshutoshChoudhary's blog

[Question] — Sum of value of GCD for all possible pairs
By AshutoshChoudhary, history, 3 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
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it -7 Vote: I do not like it

u can use gcd convulation

→ Reply
  • »
    »
    3 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 ?

    → Reply
  • »
    »
    3 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

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

      please show the implementation

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it
        Spoiler
        → Reply
»
3 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

→ Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

you can look up here, recent Div 2 D question Solution by MagentaCobra

→ Reply
»
3 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....

→ Reply