自动搬运

查看原文

来自洛谷，原作者为

	Schwarzkopf_Henkal If Lenin could see us now

搬运于2025-08-24 22:30:00，当前版本为作者最后更新于2021-04-30 17:56:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是道大 nb 题，就在我开始写的时候这还是道紫题，写着写着就变成黑的了。

首先，我们观察题面，发现是求乘积为完全平方数的子集的方案数。然后我们有一个套路，如果这个子集内的所有数的质因数分解结果相加全部都是偶数，那么这一定是个完全平方数，而这个奇偶性的合并跟异或是等价的。然后想到线性基，问题等价于求使得线性基所有位为 $0$ 的方案数，这边可以略微思考一下，或者当成套路记忆，考虑到线性基是一个基，也就是说如果这个基里面有任意一个被选择了，那么最后一定至少有一位不为 $0$，设总集大小 $S_1$，线性基大小（不是最大大小，而是插进去了的个数，也即，基的大小） $S_2$，合法方案数为 $2^{S_1-S_2}$ 即 $2$ 的自由元次幂。

也就是说，我们可以处理 $n$ （$R$ 的最大值）以内的所有质数，然后以此建立线性基，暴力做，插入单个数的复杂度为 $\text O(\frac{\pi^2(n)}{\omega})$，用 bitset 做少一个 $\omega$ 应该不用多说了。这样，你就可以拿到 $\huge 50$ 分的好成绩！

但是根据质因数分解的性质，我们知道，对于一个数，大于 $\sqrt n$ 的质因数至多只有一个，并且是可以直接求出来的，那么，我们每一个数都扫一遍 $[1,n]$ 的所有质数岂不是太浪费了吗？我们可以对于每一个数只扫一遍 $[1,\sqrt n]$ 以内的质数，并且除去这些质因数，如果剩下的结果不为 $1$，那么一定是大于 $\sqrt n$ 的质数，而且是最大的质因数。我们开一个 unordered_map<int,bitset<455> > 来专门存储这部分的线性基，插入单个数的复杂度就变成了 $\text O(\frac{\pi^2(\sqrt n)}{\omega})$。这样，你就可以拿到 $\huge 50$ 分的好成绩！没错，根本没有这档部分分！

我们发现，相比于线性基的最大大小，可能的区间长度实际上非常大，也就是说，线性基非常被填满。然后我们从裤裆里掏出一个结论，当区间长度大于一个特定的值的时候，一定有一个方案使得每一个出现过的质因数都能够在线性基里面占据一个单独的位置。此处的出现，指的是作为某个数的因数出现。

于是我们可以处理出 $n$ 以内的质数并暴力检查它是否出现过。用是否有 $\frac{R}{p}\ne\frac{L-1}{p}$ $\text O(1)$ 检查。临界长度是 $\sqrt n$。

隐蔽的坑：我发过一个帖子，如果踩进那个坑里将会只剩下 $70$ 分。

#include<bits/stdc++.h>
using namespace std;
const long long Mod=998244353;
long long T,L,R,mk[10000005],pr1[114514],pr2[665000],t1,t2,S;
bitset<455>a[455];
unordered_map<int,bitset<455>>mts;
void insert(int u){
    bitset<455>v;
    for(int i=1;i<=t1&&u!=1;i++){
        while(u%pr1[i]==0){
            u/=pr1[i];
            v[i]=!v[i];
        }
    }
    if(u!=1){
        if(!mts.count(u)){
            mts[u]=v;
            S++;
            return;
        }
        v^=mts[u];
    }
    for(int i=t1;i>=1;i--)
        if(v[i]){
            if(!a[i].any()){
                a[i]=v;
                S++;
                return;
            }
            v^=a[i];
        }
}
void clear(){
    S=0;
    mts.clear();
    for(int i=1;i<=t1;i++)
        a[i].reset();
}
long long Pow(long long u,long long v){
    long long res=1;
    while(v){
        if(v&1)
            res=res*u%Mod;
        u=u*u%Mod;
        v>>=1;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for(int i=2;i<=10000000;i++)
        if(!mk[i]){
            if(i<=3200)
                pr1[++t1]=i;
            pr2[++t2]=i;
            if(1ll*i*i<=10000000)
                for(int j=i*i;j<=10000000;j+=i)
                    mk[j]=1;
        }
    cin>>T;
    while(T--){
        clear();
        cin>>L>>R;
        if(R-L+1<=7000){
            for(int i=L;i<=R;i++)
                insert(i);
        }else {
            for(int i=1;i<=t2&&pr2[i]<=R;i++)
                if(R/pr2[i]!=(L-1)/pr2[i])
                    S++;
        }
        cout<<Pow(2,R-L+1-S)<<'\n';
    }
}/*
首先，预处理根号以内的质数，
然后bitset预处理谔谔。
不过，这样不会超时吗？
对啊，它不是要求O(n)吗

看起来是个大nb题但是为什么这个只有紫
好棒/se有50分
*/