Given a positive odd integer K and two positive integers low and high, determine how many integers between low and high contain exactly K divisors.
Input
The first line of the input contains a positive integer C (0<C<100,000), the number of test cases to follow. Each case consists of a line containing three integers: K, low, and high (1<K<10000, 0<low≤ high<10^10). K will always be an odd integer.
Output
Output for each case consists of one line: the number of integers between low and high, inclusive, that contain exactly K divisors.
Example
Input:
3
3 2 49
9 1 100
5 55 235 Output:
4
2
1
询问一组(k,l,r)，意思是在数字l到r之间有多少个数字有奇数个因子
显然如果对一个x质因数分解成(大π) pi^qi 那么总因子数是(大π) (qi+1)
因为它有奇数个因数，所以所有qi都是偶数，所以x应当是完全平方数！
因此，只要枚举x，而且l和r的范围从1e10将到1e5
把一个询问(k,l,r)差分成(k,1,r)-(k,1,l-1),就可以离线搞了
然后直接从1到10w枚举每个x，计算x^2有多少个因子，更新对于一个k，当前1~k已经记录了多少个完全平方数
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<ctime>
#define LL long long
#define inf 0x7ffffff
#define pa pair<int,int>
#define pi 3.1415926535897932384626433832795028841971
using namespace std;
inline LL read()
{
LL x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
inline void write(LL a)
{
if (a<){printf("-");a=-a;}
if (a>=)write(a/);
putchar(a%+'');
}
inline void writeln(LL a){write(a);printf("\n");}
LL l,r,k,n;
int mx;
bool isprime[];
int sum[];
struct ask{int k,n,rnk;}q[];
bool operator <(ask a,ask b){return a.n<b.n;}
int cnt[];
int ans[];
inline void init()
{
memset(isprime,,sizeof(isprime));
for (int i=;i<=;i++)sum[i]=;
isprime[]=isprime[]=;
int k,l;
for (int i=;i<=;i++)
{
if (isprime[i])
{
sum[i]=;
for (int j=;i*j<=;j++)
{
isprime[i*j]=;k=;l=j;
while (l%i==){l/=i;k++;}
sum[i*j]*=*k+;
}
}
}
}
int main()
{
init();
n=read();
for (int i=;i<=n;i++)
{
int x=read(),y=ceil(sqrt(read())),z=floor(sqrt(read()));
mx=max(mx,z);
q[*i-].k=x;q[*i-].n=y-;q[*i-].rnk=-i;
q[*i].k=x;q[*i].n=z;q[*i].rnk=i;
}
sort(q+,q+*n+);
int now=;
for (int i=;i<=mx;i++)
{
cnt[sum[i]]++;
while (now<=*n&&q[now].n==i)
{
if (q[now].rnk>)ans[q[now].rnk]+=cnt[q[now].k];
else ans[-q[now].rnk]-=cnt[q[now].k];
now++;
}
}
for (int i=;i<=n;i++)printf("%d\n",ans[i]);
}
Spoj ODDDIV