两道不错的线性筛题目记录

背景

弄了一遍蓝桥杯之后,开始刷起之前搁置的牛客寒假算法基础集训营。题目做起来比我之前想的要好,模拟时写不出的题看完题解后大部分也能补一下。

第一场与第二场中都有一道线性筛的题目,在基础的线筛上加了一点小$trick$(更可能是我写题太少,没有见过)来实现帮助计算某个结果或者形成某种递推关系。感觉还是很不错的,这里记录一下。

题目

一群小青蛙呱蹦呱蹦呱

题意简述

求所有非素数次幂的数的$lcm$($n \leq 1.6 *10^8$)

赛时思路

考虑通过$gcd$去求解$lcm$,计算复杂度后发现并不好做。于是进行打表并$OEIS$查询,发现虽然有这个数列但并没有给出有用的递推式。后面观察形如质因数分解后像$2,3$,$2,3,3$,$2,3,3,3$这样的数字,只会保留$2,3,3,3$,于是想求次幂最高的数。

但当时只是想到求对于每个数,如果它不是次幂最高的那个数,就舍弃不用。没有想到最终答案$lcm$是最高次幂的乘积,形式上可以表示为$p ^ { max { a_1, a_2, \dots , a_n } } _ {1} p ^ {max { b_1, b_2, \dots, b_n } } _{2} \dots$,因此,并未做出该题。

题解

上文提到,只需要求$p ^ { max { a_1, a_2, \dots , a_n } } _ {1} p ^ {max { b_1, b_2, \dots, b_n } } _{2} \dots$,也就是说,如果有方法计算最高的次幂就能快速计算。

此处,我们对于当前求解的$p_k$的最高次幂,分两种情况:

  • $p=2$,此时若使得$2$的次幂最高,应为$2^{max _ p} * 3$。
  • $p \geq 3$,此时若使得$p$的次幂最高,应为$2 * p^{max _ p}$。

也即是说,我们可以在线性筛的过程中,每筛到一个质因子,就求解最大次幂$max _ p$,最终筛完素数,得到的就是最终答案。

另外,因为我们要求的只是非素数次幂的数,因此,可以把$1.6 10^8$的上界降低到$8 10^7$。

这是因为,一定含有除了当前筛选到的素数$p$以外的一个质因数。而最小的质因数是$2$,因此可以这样缩小上界。

代码
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
#include <bits/stdc++.h>
#define maxn 40000005
#define maxm 80000005
#define mod 1000000007
#define int long long
using namespace std;
int n, cnt, ans = 1, pri[maxn];
bool isp[maxm];
int qpow(int a, int b){
if(b == 0) return 1;
int tmp = qpow(a, b / 2);
tmp = (tmp * tmp) % mod;
if(b & 1) tmp = (tmp * a) % mod;
return tmp;
}
//使用log快速计算最大次幂
int calc(int p, int now){
if(p == 2) return qpow(p, (int)log2(1.0 * now / 3));
return qpow(p, (int)(log2(1.0 * now / 2) / log2(p)));
}
void euler(int lim){
memset(isp, true, sizeof(isp));
isp[1] = false;
for(int i = 2; i <= lim; i++)
{
if(isp[i])
{
pri[++cnt] = i;
ans = (ans * calc(i, n)) % mod;
}
for(int j = 1; j <= cnt && i * pri[j] <= lim; j++)
{
isp[i * pri[j]] = false;
if(i % pri[j] == 0) break;
}
}
}
signed main(void)
{
scanf("%lld", &n);
euler(n / 2);
if(n < 6)
printf("empty");
else
printf("%lld\n", ans);
return 0;
}

牛牛的“质因数”

题意简述

由于不太好描述,我就截图搬过来了…

image-20210223093943354

赛时思路

这题我因为有了上一题的经验,比赛时虽然$WA$了一发,但还是做出来了。

首先,观察题目,发现需要质因数分解,拼接的话可以通过质因数乘上$10^n$来实现,如果使用普通做法的话,大概率被卡成$TLE$。

考虑线性筛,线性筛有一个特性$i$ $ mod $ $pri[j]$ $== 0$,则$break$。

由此,我们知道,线性筛在筛素数的时候,若筛选到$i$最小的质因数,则会跳出。

也就是说,这里有一个递推关系可以利用!

即$F(i pri[j])=pri[j] 10^k + F(i)$,这样就可以实现一个转移,通过前面已经计算出来的数推导后面的数的$F$值。而由于这个质因数是最小的,因此,一定可以放到拼接后数字的最前面,所以可以用$10^k$来实现这个效果,这个$k$应该等于$i$的数字位数。

如果当前数字$i$是素数的话,直接使$F(i)=i$即可。

另外,我们需要边取模边计算,由于$F(i)$在取模后数字位数会改变,因此,我们需要单独维护一个数字位数的转移关系,方程与上面的非常类似。在第一次提交时,我就是因为没有考虑这一点,$WA$了一次。

代码
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
#include <bits/stdc++.h>
#define maxn 4000005
#define int long long
using namespace std;
int n, bl[maxn], bit[maxn];
int cnt, pri[maxn]; bool isp[maxn];
const int mod = 1e9 + 7;
int quickpow(int a, int b, int p){
if(b == 0) return 1;
int tmp = quickpow(a, b / 2, p);
tmp = (tmp * tmp) % p;
if(b & 1) tmp = (tmp * a) % p;
return tmp;
}
int bitc(int x){
int cnt = 0;
while(x) x /= 10, cnt++;
return cnt;
}
int calc(int nw, int r, int i){
int cnt = bitc(r);
return ((nw * quickpow(10, bit[i], mod)) % mod + r) % mod;
}
void euler(int lim){
memset(isp, true, sizeof(isp));
isp[1] = false;
for(int i = 2; i <= lim; i++)
{
if(isp[i]) pri[++cnt] = i, bl[i] = i, bit[i] = bitc(i);
for(int j = 1; j <= cnt && i * pri[j] <= lim; j++)
{
isp[i * pri[j]] = false;
bl[i * pri[j]] = calc(pri[j], bl[i], i);
bit[i * pri[j]] = bit[i] + bit[pri[j]];
if(i % pri[j] == 0)
{
break;
}
}
}
}
signed main(void)
{
scanf("%lld", &n);
euler(n);
int ans = 0;
for(int i = 2; i <= n; i++)
{
ans = (ans + bl[i]) % mod;
//printf("%lld %lld\n", i, bit[i]);
}
printf("%lld\n", ans);
return 0;
}

如果你觉得还不错,就请咕咕的作者喝杯咖啡吧QAQ