[BZOJ3944]Sum(杜教筛)

摘要:
Dujioshai实际上是这样一个公式:$$F=Hsums_{i=2}^{n}gF$$需要前缀和$F$,辅助函数是$g$和$H$,$F$、$g$和$H$分别是三个函数的前缀和。如果$G$和$H$可以在$O$时间中找到,则$F$可以在$O$中找到。$O=O$的复杂性可以通过预处理前$n^{frac{2}{3}}$的数量来实现。不可能直接记录以下$F$值数组的下标,但请注意,我们最终需要最多$O$函数值,因此我们可以将$x$保存为$n/x$中的以下值。回到这个问题上来,就是不要在内部爆炸。

3944: Sum

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 6201  Solved: 1606
[Submit][Status][Discuss]

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

Sample Output

1 1
2 0
22 -2
58 -3
278 -3
1655470 2

HINT

 

Source

 
[Submit][Status][Discuss]

最基础的杜教筛。

杜教筛实际上就是这样一个式子:$$F(n)=H(n)-sumlimits_{i=2}^{n}g(i)F(lfloorfrac{n}{i} floor)$$

设要求的是$f$的前缀和,辅助函数分别是$g$和$h$,$F$,$G$,$H$分别是三个函数的前缀和,如果能在$O(1)$的时间内求出$G$和$H$,就能在$O(n^{frac{3}{4}})$内求出$F$。复杂度$O(sumlimits_{i=1}^{sqrt{n}} sqrt{frac{n}{i}})=O(n^frac{4}{3})$,通过预处理前$n^{frac{2}{3}}$个数就可以做到$O(n^{frac{2}{3}})$了。

对于后面的$F(n)$值数组下标不可能直接记录,但是注意到我们最终需要的$F$函数值最多有$O(n^{frac{2}{3}})$个(因为$lfloor frac{lfloorfrac{a}{b} floor}{c} floor=lfloor frac{a}{bc} floor$),所以对于后面的值可以把$x$存到$n/x$里。

回到这题,不要爆int就好了。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define rep(i,l,r) for (int i=l; i<=r; i++)
 5 typedef long long ll;
 6 using namespace std;
 7 
 8 const int N=2000010,M=100010;
 9 int T,n,m,tot,p[N];
10 ll phi[N],mu[N],Phi[M],Mu[M];
11 bool vis[M];
12 
13 ll getphi(int x){ if (x<=m) return phi[x]; else return Phi[n/x]; }
14 ll getmu(int x){ if (x<=m) return mu[x]; else return Mu[n/x]; }
15 
16 void solve(int x){
17     if (x<=m) return;
18     int t=n/x,lst=1; ll p1=0,p2=0;
19     if (vis[t]) return;
20     vis[t]=1; Phi[t]=(1ll*x+1)*x>>1; Mu[t]=1;
21     while (lst<x){
22         int i=lst+1; lst=x/(x/i); solve(x/i);
23         p1+=getphi(x/i)*(lst-i+1); p2+=getmu(x/i)*(lst-i+1);
24     }
25     Phi[t]-=p1; Mu[t]-=p2;
26 }
27 
28 int main(){
29     freopen("bzoj3944.in","r",stdin);
30     freopen("bzoj3944.out","w",stdout);
31     scanf("%d",&T); m=2000000; phi[1]=mu[1]=1;
32     rep(i,2,m){
33         if (!phi[i]) p[++tot]=i,phi[i]=i-1,mu[i]=-1;
34         for (int j=1; j<=tot && i*p[j]<=m; j++)
35             if (i%p[j]==0) { phi[i*p[j]]=p[j]*phi[i]; mu[i*p[j]]=0; break; }
36                         else phi[i*p[j]]=(p[j]-1)*phi[i],mu[i*p[j]]=-mu[i];
37     }
38     rep(i,2,m) phi[i]=phi[i-1]+phi[i],mu[i]=mu[i-1]+mu[i];
39     while (T--){
40         scanf("%d",&n); memset(vis,0,sizeof(vis));
41         if (n<=m) printf("%lld %lld
",phi[n],mu[n]);
42             else solve(n),printf("%lld %lld
",Phi[1],Mu[1]);
43     }
44     return 0;
45 }

免责声明:文章转载自《[BZOJ3944]Sum(杜教筛)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇[CTSC2018]混合果汁(二分答案+主席树)KD-Tree复习笔记(BZOJ1941 &amp; BZOJ2648 &amp; BZOJ4066)下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

关于富勒富勒旗舰店 天猫Tmall.com

关于富勒-富勒旗舰店- 天猫Tmall.com Fuhlen(富勒)品牌简介 Fuhlen(富勒)是全欧洲第二大电脑公司-德国FTS技术解决中心技术合作之下,并聘请全球顶级设计公司-德国die:haptiker GmbH公司精心设计的电脑外设品牌。 “fühlen”在德语中的是“感受、感知”的含义,与英文中的“feel”同意,旨在“感知现在,创造未来”。精...

NetBeans IDE 6.8 Beta 已经可用!

NetBeans 团队非常荣幸地宣布 NetBeans IDE 6.8 Beta 已经可用。 下载 NetBeans IDE 6.8 Beta 了解更多关于 NetBeans IDE 6.8 Beta NetBeans IDE 6.8 Beta 是第一个提供对 Java EE 6 规范支持的 IDE。本次发布特性如下: Java EE 6...

第二天--设置一个数据模型

第二天--设置一个数据模型 Symfony回顾在这份长长的但是却十分有趣的指南的第一天内容中,我们了解了如何安装Symfony框架,设置一个新程序以及开发环境,并且使用了源码版本控制安全的存放源码。顺便说一句,在第一天所生成的程序源码可以在askeet的源码仓库得到:http:/...

Linux Socket学习(六)

套接口类型与协议在第一章我们看到了如何使用socketpair函数来创建一对本地套接口。在这一章我们将会了解使用socket函数来创建一个套接口。通常情况下这两个函数都有域,套接口类型,以及协议参数。这一章将会建立在前几章的基础之上,并且主要关注于socket函数调用。这包括下面的一些内容:域参数套接口类型参数协议参数指定一个套接口的域在 第一章,我们可以看...

STL中map按值(value)排序

STL中map按值(value)排序 - wanpengcoder - 博客频道 - CSDN.NET STL中map按值(value)排序 分类:C/C++2010-11-06 14:45912人阅读评论(0)收藏举报 文中的部分内容参考自互联网,感谢作者。 map默认是按照键(key)排序的。很多时候我们需要按值(value)排序,靠map里的...

JSON.stringify Function (JavaScript)

JSON.stringify Function (JavaScript) JSON.stringify Function (JavaScript) [This documentation is for preview only, and is subject to change in later releases. Blank topics are i...