博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
bzoj3944:Sum
阅读量:5214 次
发布时间:2019-06-14

本文共 2035 字,大约阅读时间需要 6 分钟。

杜教筛板子题

又是卡了一晚上的常数

我的hash实现能力似乎差了点,写出来的hash连map都不如

用了点奇技淫巧,拿unordered_map把这题A了

先考虑\(ans2\)

\[ ans2=\sum_{i=1}^{n}\mu(i) \]
看到\(\mu\)就想到了\(\mu*I=ε\)

然后由杜教筛的式子可以得(\(S(n)\)\(\sum_{i=1}^{n}\mu(i)\)

\[ S(n)I(1)=\sum_{i=1}^{n}ε(i)-\sum_{d=2}^{n}I(d)S(\lfloor \frac{n}{d} \rfloor)\\ S(n)=1-\sum_{d=2}^{n}S(\lfloor \frac{n}{d} \rfloor)\\ \]
然后考虑\(ans1\)
\[ ans1=\sum_{i=1}^{n}\phi(i) \]
由于\(\sum_{d|n}\phi(d)=n\)

所以可得\(\phi*I=id\)

同上设\(S(n)=\sum_{i=1}^{n}\phi(i)\)

\[ S(n)I(1)=\sum_{i=1}^{n}id(i)-\sum_{d=2}^{n}I(d)S(\lfloor \frac{n}{d} \rfloor)\\ S(n)=(n+1)*n/2-\sum_{d=2}^{n}S(\lfloor \frac{n}{d} \rfloor) \]
递归分块就好了

代码:

#include
#include
#include
#include
using namespace std;void read(int &x) { char ch; bool ok; for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1; for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;}#define rg registerconst int maxn=4e6+10;bool vis[maxn];int ans1,T,n,mu[maxn],tot,pri[maxn],phi[maxn],sum[maxn];tr1::unordered_map
w1;tr1::unordered_map
w;long long ans2,sum1[maxn];void prepare(){ mu[1]=1,phi[1]=1; for(rg int i=2;i<=4e6;i++) { if(!vis[i])pri[++tot]=i,mu[i]=-1,phi[i]=i-1; for(rg int j=1;j<=tot&&pri[j]*i<=4e6;j++) { vis[i*pri[j]]=1; if(!(i%pri[j])){phi[i*pri[j]]=phi[i]*pri[j];break;} else mu[i*pri[j]]=-mu[i],phi[i*pri[j]]=phi[i]*phi[pri[j]]; } } for(rg int i=1;i<=4e6;i++)sum[i]=sum[i-1]+mu[i],sum1[i]=sum1[i-1]+phi[i];}int solvemu(int n){ if(n<=4e6)return sum[n]; if(w[n])return w[n]; int ans=1; for(rg int i=2,j;i<=n;i=j+1) { j=n/(n/i); ans-=(j-i+1)*solvemu(n/i); if(j==n)break; } return w[n]=ans;}long long solvephi(int n){ if(n<=4e6)return sum1[n]; if(w1[n])return w1[n]; long long ans=(1ll+n)*n/2; for(rg int i=2,j;i<=n;i=j+1) { j=n/(n/i); ans-=(j-i+1)*solvephi(n/i); if(j==n)break; } return w1[n]=ans;}signed main(){ read(T),prepare(); while(T--) { read(n); printf("%lld %d\n",solvephi(n),solvemu(n)); }}

转载于:https://www.cnblogs.com/lcxer/p/10549066.html

你可能感兴趣的文章
解决selenium与firefox版本不兼容问题
查看>>
HSQL转化为MR过程
查看>>
Serlvet学习笔记之四—对文件的操作
查看>>
poj 2318 TOYS 2012-01-11
查看>>
关于 push 卡顿的问题
查看>>
GOOGLE突破图书馆入口IP限制之技巧
查看>>
Prolog 逻辑推导语言
查看>>
串口,网口,USB端口的选择
查看>>
软件测试人员需不需要懂代码
查看>>
网站提示:Bad Request(Invalid Hostname)错误分析
查看>>
初识关系型数据库(SQL)与非关系型数据库(NOSQL)
查看>>
AndEngine 环境配置出错解决
查看>>
传统的Ado.net 参数设置:params SqlParameter[] commandParameters
查看>>
解决miner.start() 返回null
查看>>
开发丈夫和测试妻子
查看>>
关于MFC中窗口的销毁
查看>>
一句命令快速合并 JS、CSS
查看>>
bzoj 1898: [Zjoi2005]Swamp 沼泽鳄鱼【dp+矩阵快速幂】
查看>>
bzoj 2007: [Noi2010]海拔【最小割+dijskstra】
查看>>
AGC001 C - Shorten Diameter【枚举】
查看>>