原文链接https://www.cnblogs.com/zhouzhendong/p/CF1017F.html
题目传送门 - CF1017F
题意
假设一个数 $x$ 分解质因数后得到结果 $x=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k} $
定义 $\text{exlog}_f(x) = a_1 f(p_1) + a_2 f(p_2) + ... + a_k f(p_k)$
给定 $A,B,C,D$ 表示 $f(x)=Ax^3+Bx^2+Cx+D$
求 $\sum_{i=1}^n \text{exlog}_f(i)$ 。
$n\leq 3\times 10^8,\ \ A,B,C,D\leq 10^6,\ \ $ 答案对于 $2^{32}$ 取模。
题解
考虑一个素数 $p$ 对答案的贡献。定义 $cnt(条件)$ 为 $1$~$n$ 中满足条件的数的个数。
显然，一个素数对答案的贡献是： $\sum_{i=1}^{\infty} cnt((x\mod {p^i}=0)\ and\ (x\mod {p^{i+1}}\neq 0))\times i \times f(p_i)$ 。
由于质数的个数大约在 $\cfrac{n}{\log(n)}$ 数量级，所以我们可以一个 $log$ 求上面的东西。
接下来的问题就是如何快速得到所有质数。
考虑一个大于 $3$ 的质数对于 $6$ 取模只可能是 $1$ 或 $5$ 。
这样，我们就把可能的范围缩小了 $3$ 倍。
空间限制很小，我们需要 32 位压位，然后之前又压了 $3$ 倍，空间刚好卡进 16MB。
然后就一边暴力筛出素数，一边求当前素数对于答案的贡献。
我的写法细节比较多，不推荐。可以考虑损失一点常数来做，会好写一些。
代码
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned uint;
LL read(){
LL x=0;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+ch-48,ch=getchar();
return x;
}
uint n,A,B,C,D,ans=0;
uint fff[3333533];
// 6 - 1 5
uint F(uint v){
return A*v*v*v+B*v*v+C*v+D;
}
void update(uint p){
uint m=n,d=m/p,dd,i=0;
while (p<=d){
i++;
dd=d/p;
ans+=i*(d-dd)*F(p);
d=dd;
}
ans+=(i+1)*d*F(p);
}
int main(){
memset(fff,0,sizeof fff);
n=read(),A=read(),B=read(),C=read(),D=read();
for (uint i=2,f=0,k=0;i<=n;){
uint id=k<<1;
if (f==5)
id--;
if (i>5&&((fff[id>>5]>>(id&31))&1))
;
else {
// printf("%d\n",i);
update(i);
if (i>=5){
uint ii=i,ff=f,kk=k,iid,v1=4,v2=2;
if (f==5)
swap(v1,v2);
while (1){
if (ff==1)
ii+=v1*i,ff=5;
else
ii+=v2*i,ff=1;
if (ii>n)
break;
// printf("%u %u %u\n",ii,ff,kk);
kk=(ii+1)/6;
iid=kk<<1;
if (ii%6==5)
iid--;
fff[iid>>5]|=1<<(iid&31);
}
}
}
if (i<5){
if (i==2)
i=3;
else
i=5,f=5,k=1;
}
else if (f==1)
i+=4,f=5,k++;
else
i+=2,f=1;
}
printf("%u",ans);
return 0;
}
/*
100 0 0 0 1
*/