It can be a basic problem with Mo’s algorithm.

First of all, divide every number into prime factors.

Use two pointers \(L,R\) to present the current range. When we move the pointers, we add/remove a number from the range.

This can be mantained in a convenience way, for what we only need to do is to modify the number of occurrences of each prime factor in the range.

Meanwhile, record how many prime factors’s occurrences in the range are not multiples of three. So we could figure out the answer.

Time complexity: \(O(n\sqrt n)\) with a large constant. To pass the problem, you may do some optimization, including:

• #pragma GCC optimize("Ofast")
• Sort the queries in a more efficient way. (will be explained later)
• Use two arrays for every number when diving, one cantains the prime factors, the other contains the number of each factors.
• Coding more carefully.

In fact, if you try to reduce your constant, three seconds are quite easy to pass.

How to sort the queries in a more efficient way?

In the most primitive version, for each block, the right bounds of the queries are sorted in increasing order. Easy to see, it’s still correct if we sort them in decreasing order. So we can combine them together:

bool cmp(array<int,3>x,array<int,3>y)
{
	if(x[0]/N==y[0]/N)
	{
		if((x[0]/N)&1)
			return x[1]>y[1];
		else
			return y[1]>x[1];
	}
	return x[0]<y[0];
}

The right pointer will move less in this way.