题解 P2429 【制杖题】
lmrttx
2020-12-19 15:03:53
先看清题意。
题目给的 **$p[i]$ 一定是质数**。那么：
$$k*p[i]$$
（$k$ 为正整数）
分解质因数后，一定有质因子 $p[i]$。
很好理解。
我们对每一个数**在线**处理（离线也行，代码不贴了）。统计
$k*p[i]$ 的和，记得判断是否小于 $m$ ，最后取模。
其实，这就是**线性筛法**的思想。
这里讲一下。
用 $vis[i]$ 数组统计 $i$ 是不是质数。一枚举到质数，就将它的 $k$ 倍标记为假（$k$ 为正整数）。最后统计值为真的数。$vis$ 数组初始化为真。
时间复杂度为 $O(n*logn*logn)$。
题目分析完毕。
现在贴上代码，不要复制，加了防抄袭。
```cpp
#include<bits/stdc++.h>
#define ll long long
#define mod 376544743
using namesapce std;
ll n,m,num,sum;
map<int,bool> a;//判断一个int类型的数是不是质数的标志容器
int main(){
scanf("%lld%lld",n,m);
for(register ll i=1;i<=n;i++){
scanf("%lld",num);
for(register ll j=num;j<=m;j+=num){//枚举倍数
if(!a[j]) {a[j]=true;sum+=j;//标记并统计和}
}
}
printf("%lld\n",sum%mod);//取模
return 0;
}
```
谢谢阅读！
~~PS：要是今年CSP-S T2是这题就好了......~~