如果当(R-L+1)很小时怎么做？
完全平方数的质因数分解的每个质数的质数肯定是(0)。
考虑每个数的唯一分解，把它的每个质因数模(2)后视为一个向量。
则判定是否合法，等于判定([L,R])中是否存在一个子集(S)使得(S)中的所有质因数分解向量在xor下(=0)。
答案就是(2^{自由基数量})
考虑对每个数的所有质因数分块，一个数最多只会有一个(>sqrt{n})的质因子。
所以这个数一定可以填上线性基的(>sqrt{n})的质因子的那一位。
如果遇到第一个包含某个(>sqrt{n})质因数的数，则插入到这一位。
否则把当前的数xor上对应的一位。
由线性基的性质，这样子表示出的数不变
这样子线性基的大小降低到(sqrt{n})。
考虑继续优化。
当区间大小比较大时，线性基肯定容易被填满，所以当填满时即可跳出。
这样子就能AC。
当区间大小非常大时，线性基肯定会被填满，可以枚举每个素数计算。
#include<bits/stdc++.h>
using namespace std;
#define N 10000010
#define mo 998244353
int qp(int x,int y){
int r=1;
for(;y;y>>=1,x=1ll*x*x%mo)
if(y&1)
r=1ll*r*x%mo;
return r;
}
int t,p[N],pr[N],ct,pp[N],tp,id[N],vi[N],po[10000],ok,vv[N],ii[N];
bitset<510>bt[7010],bb[7010];
void ins(bitset<510>bv){
for(int i=500;~i;i--)
if(bv[i]){
if(!bb[i][i]){
bb[i]=bv;
ok=0;
return;
}
bv^=bb[i];
}
}
signed main(){
for(int i=2;i<N;i++){
if(!vi[i]){
p[++ct]=i;
ii[i]=ct;
pr[i]=i;
}
for(int j=1;j<=ct&&p[j]*i<N;j++){
vi[p[j]*i]=1;
pr[i*p[j]]=p[j];
if(i%p[j]==0)
break;
}
}
memset(vi,0,sizeof(vi));
scanf("%d",&t);
while(t--){
int l,r,c=0;
scanf("%d%d",&l,&r);
if(r-l+1>=7000){
for(int i=1;p[i]<=r;i++)
if(r/p[i]!=(l-1)/p[i])
c++;
printf("%d
",qp(2,r-l+1-c));
continue;
}
for(int i=l;i<=r;i++){
int x=i;
while(x!=1){
if(ii[pr[x]]<=450&&!id[pr[x]]){
id[pr[x]]=++tp;
pp[tp]=pr[x];
}
if(ii[pr[x]]<=450)
bt[i-l].flip(id[pr[x]]);
x/=pr[x];
}
}
for(int i=l;i<=r;i++){
int x=i;
while(x!=1){
if(ii[pr[x]]>450&&!id[pr[x]]){
id[pr[x]]=++tp;
pp[tp]=pr[x];
}
if(ii[pr[x]]>450){
if(!vi[id[pr[x]]]){
vi[id[pr[x]]]=1;
po[id[pr[x]]]=i-l;
vv[i-l]=1;
c++;
}
else{
bt[i-l]^=bt[po[id[pr[x]]]];
}
}
x/=pr[x];
}
}
for(int i=0;i<r-l+1;i++)
if(!vv[i]){
ok=1;
ins(bt[i]);
if(!ok)
c++;
}
printf("%d
",qp(2,r-l+1-c));
for(int i=0;i<=7000;i++){
bb[i].reset();
bt[i].reset();
}
for(int i=0;i<=tp;i++){
id[pp[i]]=vi[i]=po[i]=0;
pp[i]=0;
}
for(int i=0;i<=r-l+1;i++)
vv[i]=0;
tp=0;
}
}