chirag2505's blog

Help needed in this number theory problem
By chirag2505, history, 3 years ago, In English

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]

  • Vote: I like it
  • +11
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Problem source?

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

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +9 Vote: I do not like it

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]$$$.

→ Reply
»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

→ Reply