Coprimes on segments

Revision en1, by dmkz, 2018-06-08 15:28:22

Hello, codeforces! How we can solve this problem:

We are given an array a[1...n] (n ≤ 200000, 1 ≤ a[i] ≤ 1000000) of integers and given q queries (q ≤ 200000): li, ri, xi (1 ≤ li ≤ ri ≤ n, 1 ≤ xi ≤ 1000000). For each query we need to answer how many indexes j: li ≤ j ≤ ri and gcd(a[j], x) = 1.

Here's what I got:

1) before 1.000.000 only 78.498 primes

2) each number from input have no more than 7 prime divisors, because 2 × 3 × 5 × 7 × 11 × 13 × 17 = 510.510

3) count(li, ri, xi) = count(1, ri, xi) - count(1, li - 1, xi), li > 1

Time Limit is 1.5 s, Memory Limit is 64 MB.

Example:

6
1 2 3 4 5 6
4
1 6 1 --> 6
1 6 2 --> 3
2 4 6 --> 0
3 6 10 --> 1
Tags prefix, coprime, queries

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru3 Russian dmkz 2018-06-09 20:12:49 111
en2 English dmkz 2018-06-09 20:11:51 115 Tiny change: 'n~~~~~\n\n' -> 'n~~~~~\n\n\nUPD: solved by [user:AeonHQ]\n'
ru2 Russian dmkz 2018-06-09 11:31:49 4 Мелкая правка: 'с, памяти 64 MB.\n\nЗа' -> 'с, памяти 32 MB.\n\nЗа'
ru1 Russian dmkz 2018-06-08 20:58:39 1470 Первая редакция перевода на Русский
en1 English dmkz 2018-06-08 15:28:22 811 Initial revision (published)