sabbirh654's blog

By sabbirh654, history, 3 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

| Write comment?
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

how can I solve this problem? with patience

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how can I solve this problem? look at the editorial

»
3 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)$$$.

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

    kinda like my approach right?

    • »
      »
      »
      3 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.

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

UPD: AC code

Code
  • »
    »
    3 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