Mike is a bartender at Rico's bar. At Rico's, they put beer glasses in a special shelf.…
- User
Mike is a bartender at Rico's bar. At Rico's, they put beer glasses in a special shelf. There are n kinds of beer at Rico's numbered from 1 to n. i-th kind of beer has ai milliliters of foam on it.
Maxim is Mike's boss. Today he told Mike to perform q queries. Initially the shelf is empty. In each request, Maxim gives him a number x. If beer number x is already in the shelf, then Mike should remove it from the shelf, otherwise he should put it in the shelf.
After each query, Mike should tell him the score of the shelf. Bears are geeks. So they think that the score of a shelf is the number of pairs (i, j) of glasses in the shelf such that i < j and where is the greatest common divisor of numbers a and b.
Mike is tired. So he asked you to help him in performing these requests. Input
The first line of input contains numbers n and q (1 ≤ n, q ≤ 2 × 105), the number of different kinds of beer and number of queries.
The next line contains n space separated integers, a1, a2, ... , an (1 ≤ ai ≤ 5 × 105), the height of foam in top of each kind of beer.
The next q lines contain the queries. Each query consists of a single integer integer x (1 ≤ x ≤ n), the index of a beer that should be added or removed from the shelf.
Output
For each query, print the answer for that query in one line.
Examples
Input
5 6 1 2 3 4 6 1 2 3 4 5 1
Output
0 1 3 5 6 2
Assistant
We need to solve the problem: Given array a[1..n] (n up to 2e5, a_i up to 5e5). We have q queries (q up to 2e5), each query toggles inclusion of index x in a set S (initially empty). After each query, we need to compute the number of pairs (i, j) in S with i<j such that gcd(a_i, a_j) = 1? Wait the statement says: "score of the shelf is the number of pairs (i, j) of glasses in the shelf such that i < j and where is the greatest common divisor of numbers a and b." The problem: I recall a known problem: "Coprime array queries" or "COPRIME" - but we need to be careful: The image likely shows gcd(a_i, a_j) = 1? Actually the statement: "where is the greatest common divisor of numbers a and b." Possibly they meant "gcd(ai, aj) = 1"? Wait, typical problem: "Mike and Feet" no. I've seen a problem: "Mike and GCD Issues" but maybe not. Actually, this is a known Codeforces problem: "Mike and gcd" no. Let me think: There's a problem called "MEX Queries" not.
The problem described: "the score of a shelf is the number of pairs (i, j) of glasses in the shelf such that i < j and gcd(ai, aj) = 1." Actually the image might represent the coprime symbol. So it's likely "gcd(ai, aj) = 1". Because it's a common counting problem: counting coprime pairs in a dynamic set. So we need to support insert/delete of indices and after each query output the number of coprime pairs in the current set.
But wait, the sample: Input: 5 6 1 2 3 4 6 1 2 3 4 5 1
Output: 0 1 3 5 6 2
Let's test if it's counting coprime pairs.
We have a = [1,2,3,4,6].
Queries: 1: add index 1 (value 1) -> set {1}. Pairs: none -> 0. Output 0 matches.
2: add index 2 (value 2) -> set {1,2}. Is gcd(1,2)=1? Yes. So pair count = 1. Output 1 matches.
3: add index 3 (value 3) -> set {1,2,3}. Pairs: (1,2):1, (1,3):1, (2,3): gcd(2,3)=1 -> 1. Total 3. Output 3 matches.
4: add index 4 (value 4) -> set {1,2,3,4}. Compute coprime pairs: (1,2)=1, (1,3)=1, (1,4)=1 -> gcd(1,4)=1 (2,3)=1, (2,4)= gcd(2,4)=2 not 1, (3,4)=gcd(3,4)=1. So pairs: (1,2),(1,3),(1,4),(2,3),(3,4) = 5. Output 5 matches.
5: add index 5 (value 6) -> set {1,2,3,4,5? Actually index 5 is a5=6). So set {1,2,3,4,5} values: 1,2,3,4,6. Count coprime pairs: List all pairs (i<j): 1-2:1, 1-3:1, 1-4:1, 1-5:gcd(1,6)=1 ->1 2-3:1, 2-4:2 (no), 2-5:gcd(2,6)=2 (no) 3-4:1, 3-5:gcd(3,6)=3 (no) 4-5:gcd(4,6)=2 (no) Total = (1,2),(1,3),(1,4),(1,5),(2,3),(3,4) = 6. Output 6 matches.
6: remove index 1 (since it was toggled; it was present, so remove) -> set {2,3,4,5} values: 2,3,4,6. Coprime pairs: 2-3:1, 2-4:2 no, 2-5:2 no, 3-4:1, 3-5:3 no, 4-5:2 no -> total 2. Output 2 matches.
So indeed it's count of pairs with gcd=1. So problem: dynamic set of up to 2e5 indices, each with value a_i (<=5e5). After each toggle, output number of coprime pairs.
We need to efficiently maintain count of coprime pairs.
We have up to 2e5 elements toggled. Naively recompute O(|S|^2) impossible.
Standard approach: Use inclusion-exclusion based on Möbius function. For a multiset, number of coprime pairs = total pairs - pairs that share any common prime factor? Actually count pairs with gcd=1 can be expressed via:
Let f(d) = number of elements in S divisible by d. Then the number of pairs with gcd divisible by d is C(f(d), 2). Using Möbius inversion: Number of pairs with gcd exactly equal to g is sum_{d|g} mu(d) * C(f(g/d?), hmm careful: Actually number of pairs with gcd = 1 is sum_{d>=1} mu(d) * C(f(d), 2). Because for each pair (i,j), let g = gcd(a_i,a_j). Then for each d dividing g, contribution of mu(d) to indicator that g=1 is sum_{d|g} mu(d) = [g=1]. So indeed sum_{d} mu(d) * (number of pairs with d dividing both a_i and a_j) = number of pairs with gcd=1. And number of pairs with d dividing both is C(f(d),2), where f(d) = count of numbers in S divisible by d. So we can maintain f(d) for all d (d up to max_a = 5e5) as we add/remove numbers. Then the answer after each operation is sum_{d=1..max_a} mu(d) * C(f(d),2). And we can update f(d) by incrementing/decrementing by 1 for each divisor d of a_x when toggling. Since a_i <= 5e5, each number has at most about 100 divisors? Actually maximum number of divisors for numbers up to 5e5 is around 200? 5e5 is 500000 = 2^5 5^5? Let's compute: 500000 = 5^6 * 2^6? Actually 5^6=15625, times 2^5=32 gives 500000? 1562532=500000, so it has divisors 76? Actually number of divisors for 500000: prime factorization 500000 = 5^5 * 2^5? 5^5=3125, 2^5=32, product=100000, not 500000. Wait: 500000 = 5^6 * 2^5? 5^6=15625, 2^5=32, product=500000. So exponents: 5^6 (exponent 6) and 2^5 (exponent 5) -> number of divisors (6+1)(5+1)=7*6=42. So maximum divisor count for numbers <= 5e5 is not huge; the maximum around 500k might be <200. For numbers up to 200k, max divisors ~160. So each update requires enumerating divisors of a_x, which is about up to 200, which is fine for q=2e5 => 40 million operations, okay.
But we need to quickly compute the sum after each update. The sum over d up to max_a of mu(d)C(f(d),2). C(f,2) = f(f-1)/2. So we need to update answer incrementally when f(d) changes. Initially all f(d)=0, answer=0.
When we add a number x (value a), for each divisor d of a, we update f(d) to f(d)+1. The change in answer contributed by d is: before contribution = mu(d) * C(old_f,2). After = mu(d) * C(old_f+1,2). So delta_d = mu(d) * (C(old_f+1,2) - C(old_f,2)). Compute C(old_f+1,2) - C(old_f,2) = ( (old_f+1)old_f/2 - old_f(old_f-1)/2 ) = (old_f*(old_f+1 - (old_f-1))/2 = (old_f * 2)/2 = old_f. Actually compute:
C(f+1,2) - C(f,2) = (f+1)f/2 - f(f-1)/2 = [ (f+1)f - f(f-1) ] /2 = [ f( (f+1)-(f-1) ) ]/2 = [ f*2 ]/2 = f.
So increment when f increases by 1 changes contribution by mu(d) * old_f (since new C = old C + old_f). Similarly, when f decreases by 1 (removing), delta = mu(d) * (C(f-1,2) - C(f,2)) = mu(d) * ( -(f-1) ) because C(f-1,2) = C(f,2) - (f-1) (since going down, loss is f-1). Indeed C(f,2) - C(f-1,2) = f-1, so reverse delta = - mu(d)(f-1). But careful: when f decreases from old_f to old_f-1, delta = new - old = mu(d)(C(old_f-1,2)-C(old_f,2)) = -mu(d)*(old_f-1). So we can update answer accordingly.
Thus we can maintain global answer variable ans. On addition of value a, for each divisor d of a: ans += mu[d] * f[d]; (since old_f is before increment) then f[d]++. On removal: for each divisor d of a: first f[d]-- (or before? we need old_f). So we should compute old_f = f[d]; then ans -= mu[d] * (old_f - 1); because delta = -mu[d](old_f - 1). Equivalent: before decrement, ans += mu[d] * (C(f-1,2)-C(f,2)) = -mu[d](f-1). So we can do: ans -= mu[d] * (f[d] - 1); then f[d]--. Alternatively: first f[d]--; then ans -= mu[d] * f[d]; since after decrement, old_f-1 becomes f[d], and (old_f-1) = new f? Wait, if we first decrement: new_f = old_f - 1, then delta = mu[d] * (C(new_f,2) - C(old_f,2)) = mu[d] * (C(new_f,2) - (C(new_f,2) + new_f) )? Actually C(old_f,2) = C(new_f,2) + new_f, because C(new_f+1,2) - C(new_f,2) = new_f. So C(old_f,2) = C(new_f,2) + new_f. So new contribution - old = mu[d]*(C(new_f,2) - (C(new_f,2)+new_f)) = -mu[d]*new_f. So if we decrement first then ans += -mu[d]*new_f, i.e., ans -= mu[d]*new_f. But careful: we need to apply the change after updating f. To avoid confusion, we can compute using old_f.
I'll use: on addition: for each d: ans += mu[d] * f[d]; f[d]++; on removal: for each d: ans -= mu[d] * (f[d] - 1); f[d]--.
That works.
We need to precompute mu[d] for d up to max_a (500000). Also need divisors of each a_i? But a_i up to 5e5; we could precompute for each value the list of divisors. Since n up to 2e5, we could compute divisors on the fly per query using prime factorization. But we can also precompute divisors for all numbers up to max_a? That would be O(max_a log max_a) memory and time if we generate divisor lists for each number. max_a=5e5, sum of number of divisors up to 5e5 is about n log n? Actually sum_{i=1}^{N} d(i) ~ N log N + (2γ-1)N, about 5e5 * log(5e5) ~ 5e5*13 = 6.5e6, which is acceptable. So we can precompute a list of divisors for each value from 1 to max_a. However memory: 6.5e6 ints ~ 26 MB if using int (4 bytes) plus overhead of vector storage maybe okay. But we can also compute divisors on the fly using prime factorization, but it's simpler to precompute. However need to note that we only need divisors of specific a_i values, not all numbers; but since q up to 2e5, each toggle we need divisors of a_x. So we could precompute for each a_i its divisors list and store, because each a_i is fixed. Since n up to 2e5, total sum of divisors across all a_i might be up to 2e5 * (max divisors ~ 200) = 4e7, a bit large but still maybe okay? 4e7 ints = 160 MB, borderline. So better to precompute for each value up to max_a its divisors, then for a given a_x we look up that list. That uses total memory ~ sum_{v=1}^{max_a} d(v) ~ 6e6, which is fine.
But wait: we need mu[d] and list of divisors for each a. However we might need only the divisors d of a such that mu[d] != 0? Because if mu[d] = 0, contributions are zero, we can skip them. But we still need to update f[d] for those d because future additions might use them? Actually f(d) is count of numbers divisible by d. Even if mu[d]=0, its contribution to answer is zero, so we don't need to add to ans. But we still need to update f(d) because when we later add another number, we need to know the old f(d) to compute ans increment? Wait ans increment uses mu[d]*f[d] only. If mu[d]=0, then the term is zero. However f(d) itself is not used elsewhere except for that term. So if mu[d]=0, we can completely ignore that divisor. Because the answer formula uses only mu(d) !=0, and for updating ans we only need f(d) for d with mu(d) !=0. But note that when we add a number, we need to iterate over all divisors d of a, but we only need to update f(d) for those d with mu(d) !=0? Actually if mu(d)=0, then ans doesn't change, and also f(d) is not needed for other updates because only mu(d) matters. However future updates that involve numbers divisible by d may have divisors that are multiples of d? But the contribution for a future number will be computed using its own divisors; those divisors may include d' which could be multiples of d? But f(d) is not used directly, only through the ans formula. But the ans formula is sum over all d of mu(d)*C(f(d),2). So if mu(d)=0, it contributes zero regardless of f(d). So we can safely ignore all d with mu(d)=0. That reduces the number of divisors we need to process, because mu(d)=0 when d has a squared prime factor. Many numbers have mu=0. In fact, among numbers up to 5e5, roughly 6/π^2 ~ 0.6079 are squarefree? Actually proportion of squarefree numbers is 6/π^2 ≈ 0.6079. So about 60% are squarefree. So we still have many, but it's a reduction. But simpler: we can precompute divisors for each a_i but only keep those with mu[d]!=0. Or just compute on the fly each time using factorization and generate divisors but only squarefree divisors. This can also be done.
Given constraints, we can handle full divisors; but to be safe, I'll precompute for each number its list of divisors (or just the squarefree divisors). But note that we need to be able to quickly get the divisors of a given a_x. Since n and q up to 2e5, total operations = sum of number of divisors per query. If we generate divisors on the fly each query using prime factorization of a_x, we can do it efficiently. Factorize a_x up to 5e5 using precomputed smallest prime factor (SPF). Then generate all subsets of distinct prime factors (since only squarefree divisors matter because mu(d)=0 otherwise). But careful: a divisor d of a_x might have squared primes? Actually if a_x contains a prime squared, d could also include that prime squared and still divide a_x. But if mu(d)=0, we ignore. So we only need squarefree divisors d that divide a_x. And those are precisely all combinations of distinct prime factors of a_x. Because any squarefree divisor of a_x is a product of a subset of its distinct prime factors. So we only need to consider subsets of the set of prime factors (each with exponent 1). So number of such divisors = 2^{k} where k is the number of distinct prime factors of a_x. For a_i <= 5e5, maximum distinct primes? 2357111317 > 500k? 23571113=30030, times 17=510510 >500k, so max distinct primes is 6? Actually 23571113=30030; *17=510510 >500k, so max distinct primes is 6. 2^6=64. So at most 64 squarefree divisors. That's much smaller than total divisors (up to ~200). So it's beneficial to only consider squarefree divisors (with mu(d) != 0). mu(d) will be (-1)^{k} for these squarefree divisors. So we can compute mu(d) on the fly as (-1)^{#primes}. So we can store for each a_i its list of squarefree divisors and mu(d). This reduces per operation to at most 64 updates, which is very efficient.
Thus approach: Preprocess SPF up to MAXA = 500000. For each query index x, we get a = a[x]. Factorize a to get distinct primes. Generate all subsets (including empty set? but d=1 corresponds to empty subset). d=1 is a divisor with mu(1)=1. We need to include d=1? Yes, because mu(1)=1, and 1 divides every number. So we should include d=1 as a divisor. So we need to include the subset of distinct primes, each subset gives a divisor d = product of primes in subset, and mu(d)=(-1)^{size}. For empty set, d=1, mu=1. So we will generate all 2^{k} divisors (including 1). For each such d, we update f[d] and ans accordingly.
Now we need to maintain f[d] for d up to MAXA. However note that d can be up to a_i itself, which is up to 5e5. But only squarefree d that appear as divisors of some a_i will be used; but we can still allocate array f of size MAXA+1 (500001) of integers (counts). This is fine (500k * 4 bytes = 2MB). We also need to know if a d is squarefree? But we only update f for d that are squarefree divisors of inserted numbers. So it's okay.
But careful: When we generate subsets, we need to compute d (product). That product could be up to a_i (max 5e5) so fits in int.
Now we need to handle toggling: We need to know whether index x is currently present in S. We can keep an array bool present[1..n] initially false. For each query x, if not present, we add; else remove.
We maintain ans as a 64-bit integer (since max pairs C(2e5,2) ~ 2e10, fits in 64-bit). Use long long.
Implementation details:
- Read n, q.
- Read a[1..n].
- Precompute SPF up to MAXA (500000). Use sieve.
- For each query, we need to factorize a[x] quickly. Since q up to 2e5, we could factorize on the fly each time using SPF, but we can also precompute for each a_i its list of squarefree divisors and mu(d) to avoid repeated factorization. Because the same a_i may be toggled multiple times. So we can precompute for each i (1..n) the list of (d, mu(d)) pairs. That will use at most n * 2^{k_i} memory. Worst-case if every a_i has 6 distinct primes, then total pairs = 2e5 * 64 = 12.8e6, each pair could be two ints (d and mu). That's about 12.8e6 * 8 bytes if stored as two ints? Actually we could store d (int) and mu (int, -1,0,1) but we know mu from d or from subset size. But we can compute mu on the fly as (-1)^size, so we just need d. But we also need mu(d) for the update formula; we can compute mu on the fly as we generate divisors if we store the list of d only, but then we need to know mu(d) which depends on number of primes. If we store just d, we could recompute mu(d) quickly by factoring d? That would be inefficient. Better to store both d and mu(d). However note that mu(d) can be derived from the number of prime factors of d, but that's extra work. So we store pairs (d, mu). But we could also store d and precompute mu globally up to MAXA, so we can just look up mu[d]. That might be simpler: precompute mu array for all numbers up to MAXA using sieve. Then we can just store list of divisors d (squarefree divisors) for each a_i. Since mu[d] is 0 for non-squarefree, but we are only storing squarefree ones, so mu[d] is non-zero. So we can compute mu[d] from the precomputed mu array. But then we need to compute mu array anyway. But we can also compute mu for a given d quickly if we know its prime factors? But precomputing mu array of size 500001 is cheap.
Thus steps:
-
MAX = 500000 (or max a_i). Determine maxA = max(a_i).
-
Precompute spf and mu for all numbers up to maxA.
- Initialize mu[1] = 1.
- For i from 2 to maxA, using linear sieve or classic sieve. Alternatively, we can compute mu using the standard method: for each prime p, for multiples j, update. Simpler: Use linear sieve: vector primes, spf(maxA+1), mu(maxA+1); mu[1] = 1; for i=2..maxA: if !spf[i]: primes.push_back(i); spf[i]=i; mu[i] = -1; for each p in primes: if p > spf[i] or ip > maxA break; spf[ip] = p; if (i % p == 0) { mu[ip] = 0; break; } else { mu[ip] = -mu[i]; } This works.
-
For each i (1..n), compute its distinct prime factors from a[i] using spf, deduplicate. Then generate all squarefree divisors. We can generate using recursion or iterative bitmask. Since k <= 6, we can do simple recursion. For each subset product d, we compute mu[d] from precomputed array (or we could compute mu via parity, but using precomputed ensures correctness). However note that d might be squarefree because it's product of distinct primes, so mu[d] is either 1 or -1. So we could compute mu_d = (popcount(subset) % 2 == 0) ? 1 : -1. That is easier and avoids needing mu array. So we can store for each a_i a list of (d, sign) where sign = mu(d) = (-1)^{size}. That is simpler: we compute sign as we generate subset. So for each a_i, we get its distinct primes list prime_factors. Then we generate all subsets: for mask from 0 to (1<<k)-1: d = 1; for each bit j: if mask & (1<<j): d *= prime_factors[j]; sign = (popcount(mask) % 2 == 0) ? 1 : -1; store (d, sign) in list for index i. But note: for mask=0, d=1, sign=1. However, careful: The formula for number of coprime pairs uses mu(d) * C(f(d),2). mu(1)=1. So sign for d=1 is correct. So we can store these.
Memory: total entries sum over i of 2^{k_i} <= n * 64 = up to 12.8e6. Each entry we might store as two ints (d and sign). That's 12.8e6 * 8 bytes = ~102 MB if stored as two ints per entry. That might be high but maybe okay? 102 MB is near limit but could be borderline. However we can store as vector for each i. But 12.8 million objects with overhead of vector of vectors? Each vector has its own overhead. Better to avoid storing per index if we compute divisors on the fly each query. Since q up to 2e5, and each a_i can be toggled multiple times, it's more efficient to compute divisors once per index and store, to avoid repeated factorization and subset generation. But memory could be high.
Alternatively, we can compute divisors on the fly per query using spf to factor and then generate subsets. q=2e5, each factorization takes O(log a) time and subset generation O(2^k) <= 64. So total operations: factorization per query: while dividing by spf, number of distinct primes extraction is at most 6. So it's fast. So we can do on-the-fly without precomputing per index. That saves memory. The time: 2e5 * ( factorization steps + up to 64 updates) = about 12.8 million updates, plus factorization overhead (maybe small). That's acceptable. So we can compute divisors for each query as needed.
However, note that the same a_i may be queried many times, we could compute its divisors multiple times. That's okay.
But we could also store the list of (d, sign) for each distinct a value, not per index, because a_i may repeat. But since a_i up to 5e5, number of distinct values <= 5e5. Actually n up to 2e5, so distinct values at most 2e5. We could precompute for each distinct a its divisor list. But that still memory up to sum of 2^{k} over distinct a's. In worst case all a's distinct and each has 6 primes (unlikely but possible). 2e5 * 64 = 12.8e6 pairs again. However many numbers have fewer primes. But maybe memory is okay if we store as vector of pairs? In C++, 12.8e6 pairs of ints using e.g., vector<pair<int,int>>? Each pair typically 8 bytes (two ints) plus overhead of vector? But if we store them in a single vector per value, we have 2e5 vectors overhead: each vector has small overhead (24 bytes typical). So total maybe ~12.8e68 + 2e524 = ~102 MB + 4.8 MB ~ 107 MB. Might be near memory limit (usually 256 MB, but sometimes 512 MB). Codeforces typical memory limit 256 MB. So 107 MB is okay but combined with other arrays (f, a, etc) still okay. But also we need mu array and spf etc, total maybe < 200 MB. Could be borderline but likely passes. However we can avoid this memory by computing on the fly, which is simpler and less code. Since q up to 2e5, on-the-fly is fine.
Let's analyze factorization cost: For each query, we factor a[x] by repeated division by spf. Since a <= 5e5, factorization takes at most ~6-7 divisions per prime factor, maybe up to total divisions equal to sum of exponents, but distinct primes extraction we can stop when we have all distinct primes, but we need all prime factors? For generating squarefree divisors we only need distinct primes, not exponents. So we can factor and collect distinct primes. That is done quickly.
So we choose on-the-fly.
However, we also need to handle toggles: we need to know if index x is currently in set. So present array of bool size n.
We'll maintain ans (long long). Maintain f array (int) of size MAX+1, initialized to 0.
For each query x: v = a[x]; if present[x] is false: // add // get distinct primes of v, generate squarefree divisors. vector primes; // distinct primes // factorization using spf int temp = v; while (temp > 1) { int p = spf[temp]; primes.push_back(p); while (temp % p == 0) temp /= p; } // generate subsets int k = primes.size(); // For mask from 0 to (1<<k)-1: for mask in range(0, (1<<k)): d = 1; bits = 0; // number of set bits // we can compute iteratively // but simpler: for each mask we can compute d and sign // However we need to loop 2^k times. Since k <= 6, it's fine. // To avoid recomputing for each mask many times, we could do recursion. // We'll do simple loop: int d = 1; int sign = 1; for (int i = 0; i < k; i++) { if (mask >> i & 1) { d *= primes[i]; sign = -sign; // since mu flips sign for each prime } } // Or we can precompute d and sign for each mask, but we can just compute inside loop. // Update ans and f: ans += (long long) sign * f[d]; // because mu(d) = sign; old f[d] f[d]++; } present[x] = true; else: // remove // similarly, get divisors and update. // For each divisor d (squarefree) with sign: ans -= (long long) sign * (f[d] - 1); // old f before decrement f[d]--; present[x] = false;
After updating, output ans.
But careful: In the add case, we used ans += sign * f[d]; where f[d] is the count before increment. That's correct: delta = mu(d) * old_f. Since sign = mu(d). So ans += sign * f[d]; Then f[d]++.
In remove case, we need old_f before decrement. So we can do: ans -= sign * (f[d] - 1); then f[d]--; Equivalent: ans += sign * (C(f-1,2)-C(f,2)) = -sign*(f-1). So ans -= sign*(f[d]-1); f[d]--; That works.
Check: f[d] before decrement is old_f. So old_f-1 = f[d]-1. So compute ans -= sign * (f[d] - 1); then f[d]--;.
Alternatively: ans -= sign * f[d]; f[d]--; ??? Let's derive: If we decrement first: f[d]--; new_f = old_f - 1; delta = -sign * new_f (as earlier). So ans += -sign * new_f; i.e., ans -= sign * new_f; So we could do f[d]--; ans -= sign * f[d]; (since after decrement f[d] = new_f). That is also valid and maybe simpler. But careful: In that order, we are subtracting after updating f[d]; but we need to use new_f. So code: f[d]--; ans -= sign * f[d]; That yields ans = ans - sign * (old_f-1). Same as before. However, the formula used in addition was ans += sign * f[d]; f[d]++; which is symmetrical: we could also do f[d]++; ans += sign * f[d];? Let's check: In addition, if we increment first: f[d]++; new_f = old_f+1; delta = sign * old_f? Actually delta = sign * old_f. But after increment, f[d] = old_f+1. So ans += sign * (f[d] - 1). That is also possible. But whichever is easier.
I'll use for addition: ans += sign * f[d]; f[d]++; (using old f) For removal: f[d]--; ans -= sign * f[d]; (using new f after decrement). That seems symmetric and simple. Let's verify:
- Add: before: f = old. ans += sign * old. then f = old+1. So delta = sign*old. correct.
- Remove: before: f = old. After f--, f = old-1. Then ans -= sign * (old-1) = -sign*(old-1). So net delta = -sign*(old-1). Which matches delta = -sign*(old-1). correct.
But careful: In remove, we subtract after decrement. So the order: f[d]--; ans -= sign * f[d]; This uses new f. Equivalent to ans = ans - sign*(old-1). Good.
However, note that sign = mu(d). For d=1, mu(1)=1, sign=1.
So we will implement accordingly.
Complexity: For each query, we factor v and generate up to 2^k divisors. Since k <= 6, at most 64 iterations. So total operations ~ q * (factorization + 64) = about 2e5*70 = 14e6, plus overhead. That's fine.
Edge Cases: When a_i = 1, its distinct primes list is empty, so k=0, then we have only mask 0 -> d=1, sign=1. So we handle that.
Need to precompute spf up to MAXA (max a_i). max a_i <= 5e5, but we should set MAX = 500000 or compute max from input.
Implementation steps:
- Read n, q.
- Read array a (1-indexed).
- Determine MAXA = *max_element(a.begin(), a.end()).
- Compute spf up to MAXA using linear sieve or standard sieve. Also we may compute mu if we want, but we don't need mu array if we compute sign via parity. However, it's easier to compute mu using sieve if needed; but we can compute sign directly from subset size. So we don't need mu array. So we only need spf for factorization.
But for factorization we need spf. So we compute spf only.
However, note that we need to generate distinct prime factors. We can do while (v > 1) { p = spf[v]; primes.push_back(p); while (v%p==0) v/=p; } That yields distinct primes.
But we must be careful: v might be 1. Already handled.
Implementation details:
- We'll store spf as vector of size MAXA+1.
- Compute using classic sieve: for i from 2 to MAXA: if spf[i]==0 then spf[i]=i; for primes etc. But linear sieve is fine.
Let's implement a standard sieve: vector spf(MAXA+1); for (int i = 2; i <= MAXA; i++) { if (spf[i] == 0) { spf[i] = i; for (int j = i*2; j <= MAXA; j += i) { if (spf[j] == 0) spf[j] = i; } } } This is O(N log log N) and fine for N=5e5.
Alternatively, linear sieve is faster but not necessary.
- present: vector present(n+1, false);
- f: vector f(MAXA+1, 0);
- ans: long long = 0.
For each query: cin >> x; if (!present[x]) { // add int v = a[x]; vector primes; int temp = v; while (temp > 1) { int p = spf[temp]; primes.push_back(p); while (temp % p == 0) temp /= p; } int k = primes.size(); // iterate over masks for (int mask = 0; mask < (1<<k); mask++) { int d = 1; int sign = 1; // mu(d) for (int i = 0; i < k; i++) { if (mask >> i & 1) { d *= primes[i]; sign = -sign; } } // update f[d]++; // increment first? But we need old f for ans? We'll follow our plan: // According to our plan for addition: ans += sign * f[d] (with old f) then f[d]++. // But if we do f[d]++ first, then we need ans += sign * (f[d]-1). // We can implement whichever. // Let's do: ans += sign * f[d]; f[d]++; // uses old f // So we need to use f[d] before increment. ans += sign * f[d]; f[d]++; } present[x] = true; } else { // remove int v = a[x]; vector primes; int temp = v; while (temp > 1) { int p = spf[temp]; primes.push_back(p); while (temp % p == 0) temp /= p; } int k = primes.size(); for (int mask = 0; mask < (1<<k); mask++) { int d = 1; int sign = 1; for (int i = 0; i < k; i++) { if (mask >> i & 1) { d *= primes[i]; sign = -sign; } } // For removal: f[d]--; ans -= sign * f[d]; // after decrement f is new count f[d]--; ans -= sign * f[d]; } present[x] = false; } cout << ans << "\n";
Let's test with sample.
Simulate manually with the sample.
Initialize f[1..] all 0, ans=0.
Query 1: add index 1, a=1. primes empty, k=0: mask only 0 => d=1, sign=1. f[1] initially 0. ans += 1 * 0 =0; then f[1]++ => f[1]=1. present[1]=true. Output ans=0.
Query 2: add index 2, a=2. primes = [2]. k=1. mask0: d=1, sign=1. f[1] currently 1. ans += 1 * 1 =1; then f[1]++ => f[1]=2. mask1: d=2, sign=-1. f[2] initially 0. ans += (-1)*0 =0; f[2]++ => f[2]=1. After addition, ans=1. Output 1.
Query 3: add index 3, a=3. primes=[3]. mask0: d=1, sign=1. f[1]=2 -> ans += 2 => ans=3; f[1]=3. mask1: d=3, sign=-1. f[3]=0 -> ans+=0; f[3]=1. ans=3 output 3.
Query 4: add index 4, a=4. Note a=4 = 2^2. Distinct primes? Just 2. Because we collect distinct primes only. So primes=[2]. k=1. So divisors: d=1, mu=1; d=2, mu=-1. But is d=2 squarefree? Yes, 2 is squarefree. But also divisors like 4? 4 is not squarefree (contains 2^2), mu(4)=0, so we ignore. So we only consider d=1 and d=2. That's correct because mu(4)=0, contributes nothing. So: mask0: d=1, sign=1. f[1]=3 -> ans += 3 => ans=6; f[1]=4. mask1: d=2, sign=-1. f[2]=1 -> ans += (-1)*1 = -1 => ans=5; f[2]=2. ans=5 output 5? Wait expected output is 5, yes.
Query 5: add index 5, a=6 = 2*3. primes=[2,3]. k=2. masks: 00: d=1, sign=1. f[1]=4 -> ans+=4 => ans=9; f[1]=5. 01: d=2, sign=-1. f[2]=2 -> ans+= -2 => ans=7; f[2]=3. 10: d=3, sign=-1. f[3]=1 -> ans+= -1 => ans=6; f[3]=2. 11: d=6, sign=1 (since 2 primes => mu(6)=1). f[6]=0 -> ans+=0 => ans=6; f[6]=1. ans=6 output 6. Good.
Query 6: remove index 1, a=1. primes empty. mask0: d=1, sign=1. According to removal: f[d]--; ans -= sign * f[d] (after decrement). Initially f[1]=5. f[1]-- -> f[1]=4. ans -= 1 * 4 => ans=6-4=2. ans=2 output 2. matches.
So algorithm works.
However, careful: In removal, we decrement then subtract sign * new f. But we must be careful about the order of loops: we must ensure that for each divisor d we update accordingly. Since we are updating f and ans for each divisor, it's correct as long as we do it consistently. For removal we used f[d]--; ans -= sign * f[d]; That is fine because after decrement, f[d] is the new count. It is equivalent to ans = ans - sign * (old_f - 1). So it matches.
But is it necessary to consider all squarefree divisors? Yes, because non-squarefree d have mu(d)=0, so they contribute nothing. So ignoring them is fine.
However, there's a subtlety: The formula sum_{d} mu(d) * C(f(d),2) counts pairs with gcd=1, but f(d) is defined as number of elements divisible by d. If we only update f(d) for squarefree d, is that sufficient? Because when we compute C(f(d),2) for non-squarefree d, they have mu(d)=0, so we don't need to add them. But what about the f(d) values for squarefree d: we are updating them only when we add numbers divisible by d. But if a number is divisible by d, it is also divisible by any divisor of d? For example, consider d=6 (squarefree, product of primes 2 and 3). When we add a number that is divisible by 6, we will increment f(6) as we generate divisor 6. However, that number is also divisible by 2 and 3, and we will increment f(2) and f(3) because we also generate those divisors. So f(2) counts numbers divisible by 2, which includes numbers divisible by 6. That's correct. So we are correctly updating f(d) for all squarefree d that divide the number. For non-squarefree d, we never update f(d) nor use them; but they are not needed because mu(d)=0. So the formula holds.
But wait: Are we missing any d that are squarefree but not a product of distinct primes that are exactly the set of primes dividing the number? Actually for a given number, its squarefree divisors are exactly the d such that d divides the number and d is squarefree. So we are covering all d for which mu(d) != 0 and d divides the number. So we correctly update f(d) for all d with mu(d) != 0 that divide the number. So the sum over all d with mu(d)!=0 of mu(d)*C(f(d),2) gives number of coprime pairs.
So algorithm is correct.
Complexity: O((n+q) * sqrt?) No, O(q * (D + factorization)) where D <= 64. Good.
Implementation details: we need to generate subsets efficiently. Since k is small, we can use recursion or iterative mask. We'll use loop for mask.
However, note that for each query we recompute the prime factorization each time. Could be a bit heavy but fine. But we must ensure that we handle numbers up to 5e5. We'll precompute spf.
But we also need to handle the case a_i = 1. Factorization gives no primes, k=0, loop over mask runs from 0 to 0 (i.e., one iteration). Works.
Memory: f array size maxA+1, int, ~2 MB. spf array size ~2 MB (int). a array size n ints ~0.8 MB. present bool ~0.25 MB. So total < 10 MB.
Time: precomputing spf O(maxA log log maxA) ~ 5e5 * something.
Edge Cases: When we generate d, it may be up to a_i (max 5e5). That's within array bounds.
However, we need to be careful about integer overflow in ans. ans can be up to C(2e5,2)=~2e10, which fits in long long (9e18). So safe.
Potential pitfalls: The removal order: we do for each divisor: f[d]--; ans -= sign * f[d]; But if we process multiple divisors, the order shouldn't matter because each divisor's update is independent and uses f[d] after decrement, which is correct. However, we must be careful that we are using the same sign for each divisor. sign = mu(d) computed as (-1)^{#bits}. But is mu(d) for squarefree d indeed (-1)^k? Yes.
But is it possible that the divisor d we generate is not squarefree? Since we multiply distinct primes, it's squarefree by construction. So mu(d) = (-1)^{k}. Good.
So the solution is ready.
But wait: Check for number like a=12 = 2^2 * 3. Distinct primes: 2,3. Divisors: 1,2,3,6. All are squarefree. Good.
For a=18 = 2 * 3^2 -> distinct primes: 2,3 -> divisors 1,2,3,6.
For a=30 = 235 -> divisors: 1,2,3,5,6,10,15,30. All squarefree.
So correct.
Now consider the inclusion-exclusion correctness: The formula sum_{d} mu(d) C(f(d),2) works. But we are only summing over squarefree d. Since mu(d)=0 for non-squarefree, it's fine.
So solution works.
However, there is nuance: In the addition formula, we used ans += mu(d) * f(d) before increment. That's based on delta = mu(d) * old_f. That's correct because C(f+1,2) - C(f,2) = f. But does this hold for all pairs? Yes, because the term in the total sum for each d is mu(d) * C(f(d),2). When f(d) changes by 1, the change is mu(d) * (C(f+1,2)-C(f,2)) = mu(d) * f.
So it's fine.
Implementation with loops:
// Precompute spf int MAXA = 500000; // could compute max from input. vector spf(MAXA+1);
for (int i = 2; i <= MAXA; ++i) { if (spf[i] == 0) { spf[i] = i; if ((long long)i * i <= MAXA) { // classic sieve for (int j = ii; j <= MAXA; j += i) { if (spf[j] == 0) spf[j] = i; } } } } But note that the above only sets spf for composite numbers that are multiples of i starting from ii. But for numbers less than ii that are composite, they might have been set by smaller primes. That's okay. However we need spf for all numbers. A simpler approach: initialize spf[i]=i for i from 2 to MAXA, and for each i if spf[i]==i then for j=i2; j<=MAXA; j+=i if spf[j]==0 set spf[j]=i. This is O(N log log N) and easier.
Let's implement:
vector spf(MAXA+1); for (int i = 2; i <= MAXA; ++i) { if (spf[i] == 0) { spf[i] = i; for (int j = i*2; j <= MAXA; j += i) { if (spf[j] == 0) spf[j] = i; } } }
This works but note that for prime i, we set spf[i]=i, and for multiples, assign if not set. But note that for composite numbers, spf might be set multiple times? Since we only set if spf[j]==0, it's set to the smallest prime divisor because we iterate i from 2 upward, so the first prime that divides j will set it, which is the smallest prime divisor. So it's correct.
But we can also use linear sieve for efficiency.
I'll use linear sieve:
vector primes; spf.resize(MAXA+1, 0); for (int i = 2; i <= MAXA; ++i) { if (spf[i] == 0) { spf[i] = i; primes.push_back(i); } for (int p : primes) { if (p > spf[i] || i * p > MAXA) break; spf[i * p] = p; } }
This yields spf for each composite. For prime i, spf[i]=i.
That's fine.
Then for each query we factorize using spf:
int val = a[x]; vector pfs; while (val > 1) { int p = spf[val]; pfs.push_back(p); while (val % p == 0) val /= p; }
But note: If a[x] is 1, loop doesn't run, pfs empty.
Then generate subsets. Since k small, we can generate using recursion or iterative loops.
We must be careful: For numbers with repeated primes, the while loop will push the prime only once because we divide out all factors? Actually we do while (val % p == 0) val /= p; So after that, p won't appear again. That's correct.
Now for the subset generation, we can do:
int k = pfs.size(); for (int mask = 0; mask < (1 << k); ++mask) { int d = 1; int bits = 0; for (int i = 0; i < k; ++i) { if (mask & (1 << i)) { d *= pfs[i]; bits++; } } int sign = (bits % 2 ==