brown-Rang's blog

A Problem
By brown-Rang, history, 4 months ago, In English

Problem statement,

you are given an array of positive integers of size n, and an integer k.
for each pair of (i, j) in the array, where 1 <= i <=n and 1 <= j <=n, m is the minimum value such that lcm(a[i], a[j]) * m is a multiple of k.
you need to find the sum of values of m. i.e find the m for each pair and then take the sum of these value.

$$${s} = \sum_{i=1}^{n}\sum_{j=1}^n {m}$$$

constraints:
$$${1} \leq{n} \leq{10}^{5}$$$
$$${1} \leq{k} \leq{10}^{6}$$$
$$${1} \leq{a[i]} \leq{10}^{9}$$$

I encountered this problem in an OA.

if anybody can provide solution to this, I would be very happy.
Thanks In Advance!

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by brown-Rang (previous revision, new revision, compare).

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

I'm not used to writing solutions with Markdown syntax, and English is not my first language, so sorry if this solution is unclear.

let $$$d[i]$$$ be the minimum number $$$x$$$ so that $$$a[i]*x$$$ is divisible by $$$k$$$. Then for each pair $$$(i,j), m = gcd(d[i],d[j])$$$.

We can reduce the problem to an easier problem, calculating $$${s} = \sum_{i=1}^{n}\sum_{j=1}^n {gcd(d[i],d[j])}$$$

Notice that $$$k<=1e6$$$, that also means $$$d[i]<=1e6$$$, we just need to count how many pairs $$$(i,j)$$$ that makes $$$gcd(d[i],d[j]) = x$$$ for each $$$x$$$ from $$$1$$$ to $$$1e6$$$

Let $$$cnt[x]$$$ be how many $$$d[i]$$$ are divisible by $$$x$$$.

Let $$$f(x)$$$ be how many pairs $$$(i,j)$$$ that has $$$gcd(d[i],d[j]) = x$$$ and $$$(i!=j)$$$

we have the formula: $$$f(x) = (cnt[x]-choose-2) - f(x*2) - f(x*3) -...$$$

you can calculate $$$f$$$ in $$$O(k*log(k))$$$, and from there you just need to sum up all $$$f(x)$$$.

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    what is choose in the $$${f(x)}$$$ formula ?

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

      sorry i dont know the markdown syntax

      a choose b means how many ways to choose b elements from a elements. i think some people write it as $$$aCb$$$.

      so the main idea of the formula is that you pick 2 index $$$(i,j)$$$ from $$$cnt[x]$$$ numbers divisible by $$$x$$$. Then $$$gcd(d[i],d[j])$$$ is divisible by $$$x$$$, so you minus $$$f(x*2), f(x*3),...$$$ so you end up with the number of pairs with $$$gcd(d[i],d[j])$$$ equal to EXACTLY $$$x$$$

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

De shaw?

→ Reply