题目描述

杜老师可是要打+∞年World Final的男人，虽然规则不允许，但是可以改啊！

但是今年WF跟THUSC的时间这么近，所以他造了一个idea就扔下不管了……

给定L,R，求从L到R的这R−L+1个数中能选出多少个不同的子集，满足子集中所有的数的乘积是一个完全平方数。特别地，空集也算一种选法，定义其乘积为1。

由于杜老师忙于跟陈老师和鏼老师一起打ACM竞赛，所以，你能帮帮杜老师写写标算吗？

输入格式

从标准输入读入数据。

每个测试点包含多组测试数据。

输入第一行包含一个正整数 T(1≤T≤100)，表示测试数据组数。

接下来T行，第i+1行两个正整数Li,Ri表示第 i 组测试数据的 L,R ，保证1≤Li≤Ri≤107。

输出格式

输出到标准输出。

输出T​行，每行一个非负整数，表示一共可以选出多少个满足条件的子集，答案对998244353​取模。

---

 $R_{i} \le 1e7$ , $T \le 100$ , $\sum_{i=1}^{T}(R_{i}-L{i}+1) \le 6e7$

• 题解

  • 唯一分解，把每个质数看成一个元，$mod2$意义下高斯消元设自由元个数为$d$
  • 答案就是线性相关的子集数$=2^d$;
  • 暴力$50$
  • 在$L,R$比较大的时候，直接消元会很浪费，考虑剪枝；
  • 如果$[L,R]$中出现了质因子$p$；
  • 一 ，若 $p > \sqrt R$则$p$对应位一定有基；  ->  $p^k>R  \  (k>1)$
  • 二 ，若$ p <= \lfloor \frac{R}{L} \rfloor $ 则$p$对应位一定有基；->  $( B(L) xor  B(L*p) == B(p) )$，说明$p$独立
  • 三， 若$R-L>=6e3$，则$p$对应位一定有基;  ->  ？？？？  如果有人知道为什么的话求教
  • 大于根号的因子只有一个，特判一的；
  • 所以近距离暴力高斯消元，远距离直接计算；
  • $trick$ ：线筛每个数的因子可$logR$分解因数 ，$bitset$优化，同时线性基满了就不再插入；
  • $O(R \ + \  \sum R_{i}-L_{i}  \ + \ T*(\frac{R}{64} + 6e3*log \ R) )$
  • 1 #include
              
                2 #define ll long long 3 using namespace std; 4 const int N=60010,M=1e7+10,mod=998244353; 5 int T,L[110],R[110],n,k,size,pos[N]; 6 int pt,pr[M],vis[M],v[M],visT[M]; 7 typedef bitset<500> BIT;  8 BIT B[500],now,pre; 9 struct data{10     int x,y;11     bool operator <(const data&A)const{12         return y < A.y;13     }14 }A[N];15 int pw2(int y){16     int re=1,x=2;17     for(int i=y;i;i>>=1,x=(ll)x*x%mod){18         if(i&1)re=(ll)re*x%mod;19     }20     return re;21 }22 void get_fac(int x,BIT&y){23     y.reset(); 24     if(v[x]>k)x/=v[x];25     while(x!=1){26         int t=v[x],cnt=0;27         while(x%t==0&&(x/=t))cnt++;28         if(cnt&1)y[pos[t]]=1;29     }30 }31 bool ins(BIT&x){32     for(int i=0;i
               
                k&&visT[v[i]]!=T){55         visT[v[i]]=T;56         tot++;57     }58     for(int i=1;i<=size;i++)if((l-1)/pr[i]
                
                 =6000)solve2(L[i],R[i]);83         else solve1(L[i],R[i]);84     } 85     return 0;86 }