背景
弄了一遍蓝桥杯之后，开始刷起之前搁置的牛客寒假算法基础集训营。题目做起来比我之前想的要好，模拟时写不出的题看完题解后大部分也能补一下。
第一场与第二场中都有一道线性筛的题目，在基础的线筛上加了一点小$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;
}
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;
}
|
题意简述
由于不太好描述，我就截图搬过来了…
赛时思路
这题我因为有了上一题的经验，比赛时虽然$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\n", ans);
return 0;
}
|