网站建设宏观环境,手机网站设计报价,wordpress 滑动 评论,网址大全直接下载求$\sum_{i1}^{n}\varphi (i)$#xff0c;$n\leqslant 1e10$。 这里先把杜教筛的一般套路贴一下#xff1a; 要求$S(n)\sum_{i1}^{n}f(i)$#xff0c;而现在有一数论函数$g(i)$#xff0c;$g(i)$的前缀和很无脑#xff0c;且$f$和$g$的狄利克雷卷积的前缀和很无脑#xf… 求$\sum_{i1}^{n}\varphi (i)$$n\leqslant 1e10$。 这里先把杜教筛的一般套路贴一下 要求$S(n)\sum_{i1}^{n}f(i)$而现在有一数论函数$g(i)$$g(i)$的前缀和很无脑且$f$和$g$的狄利克雷卷积的前缀和很无脑太巧了吧。。那么由 $\sum_{i1}^{n}\sum_{d|i}f(d)g(\frac{i}{d})$ 闪一句常用套路设$ikd$转而枚举$k$。 $\sum_{k1}^{n}g(k)\sum_{d1}^{\left \lfloor \frac{n}{k} \right \rfloor}f(d)$ $\sum_{k1}^{n}g(k)S(\frac{n}{k})$ 可得 $g(1)S(n)\sum_{i1}^{n}\sum_{d|i}f(d)g(\frac{i}{d})-\sum_{k2}^{n}g(k)S(\left \lfloor \frac{n}{k} \right \rfloor)$ 进而递推求S。 官方复杂度假如构造的卷积的前缀和和g的前缀和都是O(1)可知由于S那个除法的取值范围12……m-1mn/mn/(m-1)……n 可以想到预处理一部分再算一部分假设预处理了$n^k$那么总的复杂度就是$max(n^k,没预处理的那一段)$ 没预处理的那段就是$\sum_{i1}^{n^{1-k}}\sqrt{\frac{n}{i}}n^{\frac{1}{2}}\sum_{i1}^{n^{1-k}}i^{-\frac{1}{2}}\approx n^{\frac{1}{2}}n^\frac{1-k}{2}$ 所以总的复杂度就是$max(n^k,n^{\frac{1}{2}}n^\frac{1-k}{2})$当$\frac{1}{2}\frac{1-k}{2}k$时取得最小复杂度$k\frac{2}{3}$. 然而我这里有点不懂因为没预处理的那段我们是直接递归记忆化的那记忆化的那部分复杂度怎么算如何证明杜教筛过程中出现的数字个数的上限暂不知。先用着。 好那这道题我们要找一个前缀和无脑且和$\varphi $乘起来无脑的一个函数--1——就是f(x)1不知道叫什么——因为有$\varphi *1Id$$Id(x)x$。 那就带进去玩一玩 $\sum_{i1}^{n}\sum_{d|i}\varphi (d)\sum_{k1}^{n}1\sum_{d1}^{\left \lfloor \frac{n}{k} \right \rfloor}\varphi (d) \sum_{k1}^{n}S(\left \lfloor \frac{n}{k} \right \rfloor)$ 玩够一百下再玩一百下 $S(n)\sum_{i1}^{n}\sum_{d|i}1*\varphi (d)-\sum_{k2}^{n}S(\left \lfloor \frac{n}{k} \right \rfloor)\frac{n(n1)}{2}-\sum_{k2}^{n}S(\left \lfloor \frac{n}{k} \right \rfloor)$。 OK丢去筛吧。 1 #includestring.h2 #includestdlib.h3 #includestdio.h4 #includemath.h5 //#includeassert.h6 #includealgorithm 7 //#includeiostream8 //#includebitset9 using namespace std;
10
11 #define LL long long
12 LL n,m;
13 #define maxn 5000011
14 const int mod1e97;
15 int phi[maxn],sumphi[maxn],prime[maxn/10],lp; bool notprime[maxn];
16 void pre(int n)
17 {
18 lp0; phi[1]1; sumphi[1]1;
19 for (int i2;in;i)
20 {
21 if (!notprime[i]) {prime[lp]i; phi[i]i-1;}
22 sumphi[i]sumphi[i-1]phi[i];
23 sumphi[i]-sumphi[i]mod?mod:0;
24 for (int j1,tmp;jlp 1ll*prime[j]*in;j)
25 {
26 notprime[tmpi*prime[j]]1;
27 if (i%prime[j]) phi[tmp]1ll*phi[i]*(prime[j]-1)%mod;
28 else {phi[tmp]1ll*phi[i]*prime[j]%mod; break;}
29 }
30 }
31 }
32
33 struct Edge{LL to; int v,next;};
34 #define maxh 1000007
35 struct Hash
36 {
37 int first[maxh],le;Edge edge[maxn];
38 Hash() {le2;}
39 void insert(LL y,int v)
40 {int xy%maxh; Edge eedge[le]; e.toy; e.vv; e.nextfirst[x]; first[x]le;}
41 int find(LL y)
42 {
43 int xy%maxh;
44 for (int ifirst[x];i;iedge[i].next) if (edge[i].toy) return edge[i].v;
45 return -1;
46 }
47 }h;
48
49 int du(LL n)
50 {
51 if (nm) return sumphi[n];
52 int tmph.find(n); if (tmp!-1) return tmp;
53 LL tot0;
54 for (LL i2,last;in;ilast1)
55 {
56 lastn/(n/i);
57 tot(last-i1)*du(n/i)%mod;
58 tot-totmod?mod:0;
59 }
60 LL ans(n%mod)*((n1)%mod)%mod*((mod1)1)%mod-tot;
61 ansans0?mod:0;
62 h.insert(n,ans);
63 return ans;
64 }
65
66 int main()
67 {
68 scanf(%lld,n);
69 m(LL)pow(pow(n,1.0/3),2); pre(m);
70 printf(%d\n,du(n));
71 return 0;
72 } View Code 转载于:https://www.cnblogs.com/Blue233333/p/8315576.html
