BZOJ_3944_Sum_杜教筛
Description
Input
一共T+1行
第1行为数据组数T(T<=10)
第2~T+1行每行一个非负整数N，代表一组询问
Output
一共T行，每行两个用空格分隔的数ans1,ans2
Sample Input
6
1
2
8
13
30
2333
1
2
8
13
30
2333
Sample Output
1 1
2 0
22 -2
58 -3
278 -3
1655470 2
学习下杜教筛，推一波式子。
首先有反演式子$\sum\limits_{d|n}\varphi(d)=n$
$\sum\limits_{i=1}^{n}\sum\limits_{d|i}\varphi(d)=\frac{n*(n+1)}{2}$
约数$j$出现了$n/j$次，故约数$j$将会在$i=n/j$时停止枚举。
相当于第$i$次枚举$1$到$n/i$中的数即可。
$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{\lfloor n/i\rfloor}
\varphi(j)=\frac{n*(n+1)}{2}$
$\sum\limits_{i=1}^{n}sum[n/i]=\frac{n*(n+1)}{2}$
$sum[n]+\sum\limits_{i=2}^{n}sum[n/i]=\frac{n*(n+1)}{2}$
然后记忆化搜索，每次可以分块求，总时间复杂度$O(n^{\frac{3}{4}})$。
根据均值不等式，预处理出$n^{\frac{2}{3}}$内的答案再用上面的式子能够最优。
总时间复杂度$O(n^{\frac{2}{3}}logn)，log$是$map$带来的。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
ll prime[3000050],cnt,phi[3000050],miu[3000050],summiu[3000050];
ll sumphi[3000050];
bool vis[3000050];
map<ll,pair<ll,ll> >f;
map<ll,pair<ll,ll> >::iterator it;
void init() {
int i,j;
vis[1]=phi[1]=sumphi[1]=miu[1]=summiu[1]=1;
for(i=2;i<=3000000;i++) {
if(!vis[i]) {
prime[++cnt]=i;
phi[i]=i-1;
miu[i]=-1;
}
for(j=1;j<=cnt&&i*prime[j]<=3000000;j++) {
vis[i*prime[j]]=1;
if(i%prime[j]==0) {
phi[i*prime[j]]=phi[i]*prime[j];
miu[i*prime[j]]=0;
break;
}
miu[i*prime[j]]=-miu[i];
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
sumphi[i]=sumphi[i-1]+phi[i];
summiu[i]=summiu[i-1]+miu[i];
}
}
void query(ll n,ll &ans1,ll &ans2) {
if(n<=3000000) {
ans1=sumphi[n]; ans2=summiu[n];
return ;
}
it=f.find(n);
if(it!=f.end()) {
ans1=it->second.first; ans2=it->second.second;
return ;
}
ll i,lst;
ll tmp1,tmp2;
ans1=n*(n+1)/2; ans2=1;
for(i=2;i<=n;i=lst+1) {
lst=n/(n/i); query(n/i,tmp1,tmp2);
ans1-=(lst-i+1)*tmp1; ans2-=(lst-i+1)*tmp2;
}
f[n]=make_pair(ans1,ans2);
}
int main() {
init();
int T;
ll n,ans1,ans2;
scanf("%d",&T);
while(T--) {
scanf("%lld",&n);
query(n,ans1,ans2);
printf("%lld %lld\n",ans1,ans2);
}
}