Can GCD Sum be calculated faster ?

Can anyone help me in calculating gcd sum of any number .

Function
F
F is defined as,

$
F
(
x
)

G
C
D
(
1
,
x
)
+
G
C
D
(
2
,
x
)
+
.
.
.
+
G
C
D
(
x
,
x
)
$

An array having N elements . Compute the F(x) of any element of given array .

There is two type of queries :

  1. C i : Compute F(i) , i is index of array.

  2. U i x : Update i-th element of array with x i.e. A[i] = x

The problem is with constraints

1 ≤ N ≤ 10^ 6 \\ 1 ≤ A i ≤ 5 ⋅ 10^ 5 \\ 1 ≤ Q ≤ 10^ 5

If I pre-compute F(x) for all elements using formula ∑dϕ(n/d) where d is divisors of n using formula given by this OEIS .The complexity would be O(Nsqrt(A_i)) . Is there any better method to do so?

You can also calculate ( precompute ) all the GCD sums using sieve and ETF
Refer to this editorial https://www.hackerearth.com/problem/algorithm/akash-and-gcd-1-16/editorial/

1 Like

Precompute the answer for all values of A[i] instead. You can use a sieve-like approach to calculate it and then answer the queries in O(1).

@pranavarora , what will be complexity for calculating F(x) after using sieve ? Even after getting all divisors I have to calculate ∑dϕ(n/d) ?

heyy thanks