Блог пользователя sabbirh654

Автор sabbirh654, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

how can I solve this problem? with patience

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how can I solve this problem? look at the editorial

»
4 года назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

UPD: AC code

Code