sabbirh654's blog

all pair gcd product
By sabbirh654, history, 4 years ago, In English

how can I solve this problem? Any hints ? here is the problem link :

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

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

how can I solve this problem? with patience

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

how can I solve this problem? look at the editorial

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

Let's have $$$f(n, x) = gcd(1, x) * gcd(2, x) * ... gcd(n, x)$$$. Then answer is $$$f(n, 1) * f(n, 2) * ... * f(n, m)$$$

Since $$$g(x) = gcd(a, x)$$$ is multiplicative function over $$$x$$$ then $$$f(x) = f(n, x)$$$ is multiplicative function over $$$x$$$ too. So you can calculate all $$$f(x)$$$ for $$$x$$$ in $$$[1..m]$$$ for $$$O(m)$$$.

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

    kinda like my approach right?

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

      Not really sure how your approach works and implements. But maybe in nutshell they same. I don't mean any inclusion/exclusion, just dp.

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

UPD: AC code

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

    You need just for linear time calculate factorization of all numbers. Click

    → Reply