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 :
-
C i : Compute F(i) , i is index of array.
-
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?