Spoj-ODDDIV Odd Numbers of Divisors

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已经记录了多少个完全平方数

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<queue>
 8 #include<deque>
 9 #include<set>
10 #include<map>
11 #include<ctime>
12 #define LL long long
13 #define inf 0x7ffffff
14 #define pa pair<int,int>
15 #define pi 3.1415926535897932384626433832795028841971
16 using namespace std;
17 inline LL read()
18 {
19     LL x=0,f=1;char ch=getchar();
20     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
21     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
22     return x*f;
23 }
24 inline void write(LL a)
25 {
26     if (a<0){printf("-");a=-a;}
27     if (a>=10)write(a/10);
28     putchar(a%10+'0');
29 }
30 inline void writeln(LL a){write(a);printf("
");}
31 LL l,r,k,n;
32 int mx;
33 bool isprime[100010];
34 int sum[100100];
35 struct ask{int k,n,rnk;}q[200010];
36 bool operator <(ask a,ask b){return a.n<b.n;}
37 int cnt[1324];
38 int ans[100010];
39 inline void init()
40 {
41     memset(isprime,1,sizeof(isprime));
42     for (int i=1;i<=100000;i++)sum[i]=1;
43     isprime[0]=isprime[1]=0;
44     int k,l;
45     for (int i=2;i<=100000;i++)
46     {
47         if (isprime[i])
48         {
49             sum[i]=3;
50             for (int j=2;i*j<=100000;j++)
51             {
52                 isprime[i*j]=0;k=1;l=j;
53                 while (l%i==0){l/=i;k++;}
54                 sum[i*j]*=2*k+1;
55             }
56         }
57     }
58 }
59 int main()
60 {
61     init();
62     n=read();
63     for (int i=1;i<=n;i++)
64     {
65         int x=read(),y=ceil(sqrt(read())),z=floor(sqrt(read()));
66         mx=max(mx,z);
67         q[2*i-1].k=x;q[2*i-1].n=y-1;q[2*i-1].rnk=-i;
68         q[2*i].k=x;q[2*i].n=z;q[2*i].rnk=i;
69     }
70     sort(q+1,q+2*n+1);
71     int now=1;
72     for (int i=0;i<=mx;i++)
73     {
74         cnt[sum[i]]++;
75         while (now<=2*n&&q[now].n==i)
76         {
77             if (q[now].rnk>0)ans[q[now].rnk]+=cnt[q[now].k];
78             else ans[-q[now].rnk]-=cnt[q[now].k];
79             now++;
80         }
81     }
82     for (int i=1;i<=n;i++)printf("%d
",ans[i]);
83 }

Spoj ODDDIV