Блог пользователя chirag2505

Автор chirag2505, история, 2 года назад, По-английски

Given an array of integers A of length N. For each index i, find number of indices j(j!=i) such that gcd(A[i],A[j])>1.

Constraints:
N<=1e5
1<=A[i]<=N

Example:

  1. A = [4,3,2,4] output = [2,0,2,2]

  2. A = [2,3,6,4,6,5] output = [3,2,4,3,4,0]

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Problem source?

It's standard practice to ask for a problem link to not give solutions to ongoing contests.

»
2 года назад, # |
Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится

I think this might work.

Because each $$$A[i] \leq 100,000$$$, there can be at most 6 distinct prime factors for each $$$A[i]$$$ (notice that $$$2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 > 100,000$$$).

This means that the total number of subsets of distinct prime factors is $$$\leq 2^6$$$ for each $$$A[i]$$$. Thus, for each $$$A[i]$$$, we can use inclusion-exclusion principle to compute the number of elements that are divisible by at least one of the prime factors of $$$A[i]$$$.

»
2 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

This problem is similar to this one CSES — Counting Coprime Pairs

You can apply principle of inclusion and exclusion with Möbius function to solve it.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Make a counting array — cnt[i] -> number of occurrences of number i in array.

For each number num in array, iterate over all max(A[i]) / num possible divisors, and add their sum — 1 to the answer (-1 represents your own number being removed). If you counted the answer for number num, memoize it -> let dp[num] be the answer.

Then, the complexity is as follows -> iterating for(int i = 1; i <= N; ++i) up to max A / i is O(A log A), and if you meet a number you met before, you retrieve the answer in O(1) -> O(AlogA)