题目描述

杜老师可是要打+∞年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) )$

 #include<bits/stdc++.h>

 #define ll long long

 using namespace std;

 const int N=,M=1e7+,mod=;

 int T,L[],R[],n,k,size,pos[N];

 int pt,pr[M],vis[M],v[M],visT[M];

 typedef bitset<> BIT;

 BIT B[],now,pre;

 struct data{

     int x,y;

     bool operator <(const data&A)const{

         return y < A.y;

     }

 }A[N];

 int pw2(int y){

     int re=,x=;

     for(int i=y;i;i>>=,x=(ll)x*x%mod){

         if(i&)re=(ll)re*x%mod;

     }

     return re;

 }

 void get_fac(int x,BIT&y){

     y.reset();

     if(v[x]>k)x/=v[x];

     while(x!=){

         int t=v[x],cnt=;

         while(x%t==&&(x/=t))cnt++;

         if(cnt&)y[pos[t]]=;

     }

 }

 bool ins(BIT&x){

     for(int i=;i<size;i++)if(x[i]){

         if(B[i][i])x^=B[i];

         else return B[i]=x,true;

     }

     return false;

 }

 void solve1(int l,int r){

     int tot=,cnt=,tot2=;

     for(int i=l;i<=r;i++)A[++cnt]=(data){i,v[i]};

     sort(A+,A+cnt+);

     for(int i=;i<size;i++)B[i].reset();

     for(int i=;i<=cnt;i++){

         get_fac(A[i].x,now);

         if(A[i].y<=k){if(tot<size)tot+=ins(now);}

         else if(A[i].y!=A[i-].y){tot2++;pre=now;}

         else {now^=pre;if(tot<size)tot+=ins(now);}

     }

 //    printf("%d %d\n",tot,tot2);

     printf("%d\n",pw2(r-l+-tot-tot2));

 }

 void solve2(int l,int r){

     int tot=;

     for(int i=l;i<=r;i++)if(v[i]>k&&visT[v[i]]!=T){

         visT[v[i]]=T;

         tot++;

     }

     for(int i=;i<=size;i++)if((l-)/pr[i]<r/pr[i]&&visT[pr[i]]!=T){

         visT[pr[i]]=T;

         tot++;

     }

     printf("%d\n",pw2(r-l+-tot));

 }

 int main(){

     freopen("T2.in","r",stdin);

     freopen("T2.out","w",stdout);

     scanf("%d",&T);

     for(int i=;i<=T;i++)scanf("%d%d",&L[i],&R[i]),n=max(n,R[i]);

     k=sqrt(n); v[]=;

     for(int i=;i<=n;i++){

         if(!vis[i]){

             v[pr[++pt]=i]=i;

             if(i<=k)size++,pos[i]=pt-;

         }

         for(int j=;j<=pt&&i*pr[j]<=n;j++){

             vis[i*pr[j]]=;

             v[i*pr[j]]=v[i];

             if(i%pr[j]==)break;

         }

     }

     for(int i=;T;i++,T--){

         if(R[i]-L[i]>=)solve2(L[i],R[i]);

         else solve1(L[i],R[i]);

     }

     return ;

 }

THUSC2017D1T2

老师

【THUSC2017】杜老师

题目描述

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

题解