【THUSC2017】杜老师 题解

OI/XCPC , Comments

题目大意

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

  多测，$T \leq 100$
  $1 \leq L \leq R \leq 10^7,\ \ \sum_{i=1}^T R_i-L_i+1 \leq 6 \times 10^7$
  5s

题解

  在 thu 门外哭哭的日子

  感觉一开始没有这个方向的话就想不到这个方向了。。还是说我太菜了。。

【50%】$T \leq 10,\ \ \sum R_i-L_i+1 \leq 5000$

  假设 $[1,maxR]$ 范围内的质数有 $pnum$ 个，分别为 $p_1,\cdots,p_{pnum}$。
  把每个数字 $i$ 看成一个 $pnum$ 维 01 向量 $\vec{v_i}$，其中第 $j$ 维为 $1$ 当且仅当 $i$ 含有奇数个质因子 $p_j$。
  那么原数相乘，相当于向量异或，于是就想到线性基。于是发现答案等于 $2^{R-L+1-基的数量}$。

  然后优化，质数以 $\sqrt{maxR}$ 为界分为大质数和小质数，每个数最多含有 1 个大质数，因此出现过的大质数的位置一定是基，因此线性基就只用考虑小质数了。小质数共 446 个。
  时间 $O(T (\sum R_i-L_i+1) \cdot 446 \cdot \frac{446}{64})。$

【100%】

  思考第 11、12 个数据点的条件：$R_i-Li \geq 999990$，是要说什么呢？
  是要引导发现一个性质：当区间长度 $R_i-L_i+1 \geq 2\sqrt{maxR}$ 时，所有小质数的位置都是基。

  口胡证明：相当于证明所有的小质数都与别的质数线性独立。设有小质数 $p_1$，设质数 $p_2>p_1$。
  当区间长度 $\geq 2\sqrt{maxR}$ 时，$p_1$ 至少出现两次了，且这两次里至少有一次是有 $p_1$ 而没有 $p_2$ 的，（$p_1$ 出现的间隔为 $p_1$，这个间隔不可能使 $p_2$ 也出现两次。）然后区间内必然还有数是既不含 $p_1$ 也不含 $p_2$ 的。
  也就是说，在不含 $p_2$ 的数里，既可以含有 $p_1$，也可以不含有 $p_1$，那么 $p_1$ 和 $p_2$ 就线性独立了。
  $p_1$ 取遍所有的小质数，那么就有：所有的小质数都与别的质数线性独立，因此所有小质数的位置都是基。

  这题可以偷懒直接把 $2\sqrt{maxR}$ 当成 $6000$ 省点常数。也就是区间长度 $\geq 6000$ 之后就不用做线性基了，可以扫一遍统计大质数然后输出。
  那么时间就是 $O((\sum R_i-L_i+1)+T \cdot 6000 \cdot 446 \cdot \frac{446}{64})$，满打满算应该是跑不过的，但是它跑过去了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;

const int maxn=1e7+5, sqrtn=446;
const LL mo=998244353;

int l,r;

int p0,p[maxn],minp[maxn],divp[maxn],maxp[maxn];
bool bz[maxn],cnt[maxn];
void Prime(int n)
{
	fo(i,2,n)
	{
		if (!bz[i]) p[++p0]=i, cnt[i]=1, minp[i]=maxp[i]=p0, divp[i]=1;
		fo(j,1,p0)
		{
			if ((LL)i*p[j]>n) break;
			int nxt=i*p[j];
			bz[nxt]=1;
			minp[nxt]=j;
			maxp[nxt]=maxp[i];
			if (i%p[j]==0)
			{
				cnt[nxt]=cnt[i]^1;
				divp[nxt]=divp[i];
				break;
			} else
			{
				cnt[nxt]=1;
				divp[nxt]=i;
			}
		}
	}
}

LL Pow(LL x,int y)
{
	LL re=1;
	for(; y; y>>=1, x=x*x%mo) if (y&1) re=re*x%mo;
	return re;
}

bitset<sqrtn+2> zero,base[sqrtn+2],x,f[6005];
int basenum,bignum,big[maxn];
void add()
{
	fd(i,sqrtn,1) if (x[i])
	{
		if (base[i][i]) x^=base[i]; else
		{
			base[i]=x;
			basenum++;
			break;
		}
	}
}

int T,bigP[maxn];
bool apr[maxn];
int main()
{
	Prime(10000000);
	
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d %d",&l,&r);
		
		if (r-l+1>6000)
		{
			int num=0;
			fo(i,l,r) if (maxp[i]>sqrtn && !apr[maxp[i]]) num++, apr[maxp[i]]=1;
			printf("%lld\n",Pow(2,r-l+1-num-sqrtn));
			fo(i,l,r) if (maxp[i]>sqrtn) apr[maxp[i]]=0;
		} else
		{
			basenum=bignum=0;
			fo(i,1,sqrtn) base[i]=zero;
			fo(i,l,r)
			{
				x=zero;
				for(int ii=i; ii>1; ii=divp[ii])
					if (minp[ii]>sqrtn) bigP[i]=minp[ii]; else x[minp[ii]]=cnt[ii];
				if (bigP[i] && !big[bigP[i]])
				{
					big[bigP[i]]=++bignum;
					f[bignum]=x;
				} else
				{
					if (bigP[i]) x^=f[big[bigP[i]]];
					add();
				}
				if (basenum==sqrtn) break;
			}
			printf("%lld\n",Pow(2,r-l+1-basenum-bignum));
			
			fo(i,l,r) big[bigP[i]]=0;
		}
	}
}

kqpOIACMer / HKU_CS / LLer / TCS

糖少许，盐少许