* ! THUSC2017杜老师

30分：

枚举\(\sqrt R\)的 质数，一个数，若有奇数个该质数，则该位置为1，否则为0，变成一个二进制数，我们及要求有多少个子集异或为0。插入线性基，若无法插入则将答案*2

100分：

\(R-L+1>6000\)则出现的质数都可以随便选

否则，分为两部分

对于含有大于\(\sqrt R\)的质数（每个数只能含一个）(根号调整发复杂度)，和之前含有这个质数的数消元（异或），只会异或n次，这样就只剩小于\(\sqrt R\)的了，直接插入线性基即可

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c==‘-‘)f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f==1?x:-x;
}
const int mod=998244353,N=500,M=1e7,LR=6004;
typedef long long ll;
typedef bitset<N> bit;
int tot,L,R,ans,top,mn[M],tg[M],pri[M/10],st[LR];
bit p[N],t[LR];
inline int ksm(int x,int r){
	int ret=1;
	for(int i=0;(1ll<<i)<=r;i++){
		if((r>>i)&1)ret=(ll)ret*x%mod;
		x=(ll)x*x%mod;
	} 
	return ret;
}
inline void preinit(){
	for(int i=2;i<M;i++){
		if(!mn[i]){pri[++tot]=i;mn[i]=tot;}
		for(int j=1;j<=tot&&pri[j]*i<M;j++){
			mn[pri[j]*i]=j;
			if(i%pri[j]==0)break;
		}
	}
}
inline bool insert(bit x){
	for(int i=N-1;i>=0;i--){
		if(!x[i])continue;
		if(p[i][i])x^=p[i];
		else{p[i]=x;return 1;} 
	}
	return 0;
}
inline void solve(){
	L=read();R=read();
	ans=top=0;
	if(R-L>6000){
		for(int i=1;pri[i]<=R;i++)
			if(R/pri[i]>(L-1)/pri[i])ans++;
	}
	else{
		for(int i=0;i<N;i++)p[i].reset();
		for(int i=L,x,p;i<=R;i++){
			x=i;p=i-L+1;
			t[p].reset();
			while(x>1&&mn[x]<N){
				t[p].flip(mn[x]);
				x/=pri[mn[x]];
			}
			if(x==1)ans+=insert(t[p]);
			else if(!tg[x]){tg[x]=p;ans++;st[++top]=x;}
			else{t[p]^=t[tg[x]];ans+=insert(t[p]);}
		}	
	}
	for(int i=1;i<=top;i++)tg[st[i]]=0;
	cout<<ksm(2,R-L+1-ans)<<"\n";
}
int main(){
	preinit();
	int T=read();
	while(T--)solve();
	return (0-0);
}

* ! THUSC2017杜老师

原文：https://www.cnblogs.com/aurora2004/p/12762886.html