ashu.hua's blog

[Question] — Sum of value of GCD for all possible pairs
By ashu.hua, history, 3 years 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

Comments Comments (14)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it -7 Vote: I do not like it

u can use gcd convulation

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      please show the implementation

      → Reply
      • »
        »
        »
        »
        3 years ago, hide # ^ |
        ← Rev. 2  
        Vote: I like it 0 Vote: I do not like it
        Спойлер
        → Reply
»
3 years ago, hide # |
 
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 years ago, hide # |
← 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 gotexans

→ Reply
»
3 years ago, hide # |
 
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