The problem statement (Codeforces# 385C) is this:
We are given a sequence of \$n\$ numbers, i.e. \$x_i\$ and \$m\$ queries to find how many of these are divisble by primes between two given numbers (not necessarily prime) \$l_i\$ and \$r_i\$ (inclusive).
Constraints are: \$1\le n\le 10^6, 2\le x_i \le 10^7, 2\le m \le 50000, 2\le l_i\le r_i \le 2x10^9\$
My approach is to create a map xcnt
which contains unique \$x_i\$ and their counts so as to reduce repeated efforts. I also find the maximum \$x_i\$ as maxx
. Now I sieve all odd numbers from 3 in a boolean array using Sieve of Erathosthenes and at the same time creating a map primes
and a list primelist
which contain the prime numbers and the map just contains key value pair as prime number and index to list.
Next, I create a Binary Index Tree/Fenwick Tree which is indexed by the prime numbers' index, i.e. BIT[1]
contains the count of numbers divisible by 0
th prime number which I consider as 2, then BIT[2]
contains sum of counts of numbers divisible by 2 and 3 and so on according to design of Fenwick Tree. Finally when I am given integers \$l_i\$ and \$r_i\$, I use binary search (builtin) to find the smallest and largest prime number in this range and then use BIT to find the sum of counts.
My Java based solution (works perfectly):
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;
import java.util.TreeMap;
public class P385C {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] x = new int[n];
//count of x
HashMap<Integer, Integer> xcnt = new HashMap<>();
//max of x
int maxx = 0;
for (int i = 0; i < n; i++) {
x[i] = in.nextInt();
//if not in map add (x[i],0)
if (!xcnt.containsKey(x[i])) xcnt.put(x[i], 0);
//xcnt[x[i]]++
xcnt.put(x[i], xcnt.get(x[i]) + 1);
if (x[i] > maxx) maxx = x[i];
}
int m = in.nextInt();
boolean[] notprime = new boolean[(maxx - 3) / 2 + 1];
//0->3,1->5,2->7,3->9,4->11,5->13,6->15,7->17,...n-1->2n+3=maxx
//map of (pn,n) [pn=nth prime number n=0,1,2..]
TreeMap<Integer, Integer> primes = new TreeMap<>();
List<Integer> primelist = new ArrayList<>();
int ind = 1;
primes.put(2, 0);
primelist.add(2);
for (int i = 0; 2 * i + 3 <= maxx; i++) {
if (!notprime[i]) {
long num = 2 * i + 3;
for (long j = num * num; j < maxx; j += num)
if (j % 2 == 1) notprime[(int) ((j - 3) / 2)] = true;
primes.put((int) num, ind++);
primelist.add((int) num);
}
}
BIT bit = new BIT(primes.size() + 1);
for (int xs : xcnt.keySet()) {
for (int p : primelist) {
// if p>xs no more divisibility now
if (p > xs) break;
// if xs%p then we add xcnt[xs] to f(p) in BIT by getting index from primes map
if (xs % p == 0) bit.add(primes.get(p), xcnt.get(xs));
}
}
for (int i = 0; i < m; i++) {
int l = in.nextInt();
int r = in.nextInt();
if (l <= maxx) {
//get just next or equal prime
int pmin = primes.ceilingKey(l);
//get just previous or equal prime
int pmax = primes.floorKey(r);
System.out.println(bit.sumRange(primes.get(pmin), primes.get(pmax)));
continue;
}
System.out.println(0);
}
in.close();
}
static class BIT {
int[] bit;
public BIT(int n) {
bit = new int[n];
}
public int getSum(int ind) {
int sum = 0;
ind++;
while (ind > 0) {
sum += bit[ind];
ind -= ind & -ind;
}
return sum;
}
public void add(int ind, int val) {
ind++;
while (ind < bit.length) {
bit[ind] += val;
ind += ind & -ind;
}
}
public int sumRange(int i, int j) {
return getSum(j) - getSum(i - 1);
}
}
}
Problem
- I did not think so but this solution though working correctly is not fast enough, according to my calculations I believe my complexity is \$O(n(\log{n})(\log\log{n})+m(\log{n}+\log{P})+P\log{P})\$ where \$P\$ (664,579~10^7) is the count of primes below maximum x so total operations are of order 10^8 which I think can be solved under a second under present computers (given time limit is 2 seconds).
- I would also like to welcome any other improvements that I could make or any other suggestions.