[BZOJ3601]一个人的数论-题解

【题目地址】

题意简述

给你n,d，求下面式子在mod 109+7意义下的值。

i=1∑n​[gcd(i,n)=1]id

其中n特别大，所以我们给你一个w，然后给你两个数组pi​,ci​，其中：

n=i=1∏w​pici​​

d≤100,w≤1000,pi​,ci​≤109

我们仍旧先推一波式子：

ans=====​i=1∑n​[gcd(i,n)=1]idi=1∑n​idj∣i,j∣n∑​μ(j)j=1∑n​μ(j)j∣i∑n​idj=1∑n​μ(j)i=1∑⌊jn​⌋​(ij)dj=1∑n​μ(j)jdi=1∑⌊jn​⌋​id​

后面部分就是自然数幂的前缀和，拉格朗日差值就可以了，在O(dlogd)时间内求出，而前面是可以杜教筛的：

j∣n∑​μ(j)jd=​(μ⋅idd)∗1​

我们令f=(μ⋅idd)∗1,g=idd，然后f∗g就等于：

j∣n∑​μ(j)jd(jn​)d=ndj∣n∑​μ(j)=nd[n=1]=[n=1]=ϵ

所以f=(μ⋅idd)∗1,g=idd,h=ϵ，然后套入杜教筛公式即可：

S(n)=1−i=2∑n​idS(⌊in​⌋)

然后就可以在O(n3@font-face { font-family: "autolinktags"; src: url("https://www.seowoai.com/zb_users/plugin/AutoLinkTags/style/fonts/iconfont.woff2") format("woff2"), url("https://www.seowoai.com/zb_users/plugin/AutoLinkTags/style/fonts/iconfont.woff") format("woff"), url("https://www.seowoai.com/zb_users/plugin/AutoLinkTags/style/fonts/iconfont.ttf") format("truetype"); font-weight:normal; font-style:normal; }.tagslink::after { content:"\e613"; margin:2px 0 0 0px; font-size:12px; font-family:"autolinktags"; display:inline-block; vertical-align:top; }