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.
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!
Auto comment: topic has been updated by 1.LaZyPersoN (previous revision, new revision, compare).
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)$$$.
what is
choosein the $$${f(x)}$$$ formula ?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$$$
ok, got it!
De shaw?
yeah!
did you take the OA ?
Yea, i wasn't able to solve this one too