正題

題目鏈接:https://gmoj.net/senior/#main/show/6065

---

題目大意

$oneness(x)$表示$x$的約數(shù)中全是$1$的數(shù)的個數(shù)，給出一個長度為$l$的隨機生成的數(shù)$n$，求$$\sum _{i=1}^{n}oneness(i)$$

---

解題思路

轉(zhuǎn)換一下題意就是求$$\sum _{i=2}^l?\frac{n}{\frac{10^i?1}{9}}?=\sum _{i=2}^l?\frac{9n}{10^i?1}?$$
先讓$n$乘上$9$，然后把每一位的貢獻拆成小數(shù)和整數(shù)部分，我們先來看整數(shù)部分

首先對于一個$\frac{k?10^i}{10^j?1}$那么它的值應該是在第$i?xj+1(x\in N)$位會有一個$k$。（如$\frac{10^9}{999}=1001001.001001001001001001001001$）

然后我們看這題，$j$是$1～n$的每一個值，那么對于每第$i$位我們拆成$k?10^i$會對第$i?x$位產(chǎn)生${\sigma }_0(x)$次貢獻（${\sigma }_0(x)$表示$x$的約數(shù)個數(shù)）。設$a_i$表示第$i$位的數(shù)，$f_i$表示第$i$位的答案，那么有式子$$f_i=\sum _{j=0}^{\infty }{a}_{i+j}{\sigma }_0(j)$$
這個式子可以先預處理出${\sigma }_0(j)$然后把$a$反過來就是一個卷積的式子，$FFT$優(yōu)化即可。

對于小數(shù)部分，因為在比較后的位數(shù)的產(chǎn)生貢獻概率極小，又因為數(shù)字隨機生成，所以我們直接將這些部分省略。我們只處理到小數(shù)的$12$位，和上面同理算出每一個小數(shù)位的貢獻即可。

時間復雜度$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<cstdlib> #define ll long long using namespace std; const ll N=1e6+10; const double Pi=acos(-1); struct complex{double x,y;complex(double xx=0,double yy=0){x=xx;y=yy;return;} }x[N],y[N]; ll n,m,r[N],a[N],d[N],b[N],f[N]; unsigned int sed; complex operator+(complex x,complex y) {return complex(x.x+y.x,x.y+y.y);} complex operator-(complex x,complex y) {return complex(x.x-y.x,x.y-y.y);} complex operator*(complex x,complex y) {return complex(x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x);} void fft(complex *f,ll op){for(ll i=0;i<m;i++)if(i<r[i])swap(f[i],f[r[i]]);for(ll p=2;p<=m;p<<=1){ll len=p>>1;complex tmp(cos(Pi/len),op*sin(Pi/len));for(ll k=0;k<m;k+=p){complex buf(1,0);for(ll i=k;i<k+len;i++){complex tt=f[i+len]*buf;f[i+len]=f[i]-tt;f[i]=f[i]+tt;buf=buf*tmp;}}}return; } void solve(){m=1;ll lg=0;for(;m<=2*n;m<<=1);for(ll i=0;i<=m;i++)r[i]=(r[i>>1]>>1)|((i&1)?(m>>1):0);for(ll i=1;i<=n;i++)x[i]=complex(a[n-i+1],0),y[i]=complex(d[i],0);fft(x,1);fft(y,1);for(ll i=0;i<m;i++)x[i]=x[i]*y[i];fft(x,-1);for(ll i=0;i<m;i++)f[i]=(int)(x[i].x/(double)m+0.5);return; } int main() {scanf("%lld%u",&n,&sed);for(ll i=1;i<=n;i++){a[i]=sed/1024%10;sed=sed*747796405u-1403630843u;}reverse(a+1,a+n+1);ll g=0;for(ll i=1;i<=n;i++){a[i]=a[i]*9+g;g=a[i]/10;a[i]%=10;}if(g)a[++n]=g;for(ll i=2;i<=n;i++)for(ll j=i;j<=n;j+=i)d[j]++;solve();reverse(f+1,f+n+1);ll pw[11];pw[0]=1;for(ll i=1;i<=10;i++)pw[i]=pw[i-1]*10;for(ll i=2;i<=10;i++){ll S=0;for(ll j=1;j<=n;j+=i)for(ll k=1;k<=i;k++)S+=a[j+k-1]*pw[k-1];f[1]+=S/(pw[i]-1); }for(ll i=11;i<=n;i++){for(ll j=1;j<=12;j++)b[j]=0;for(ll j=1;j<=n;j+=i)for(ll k=1;k<=11;k++)b[k]+=a[j+i+k-12];for(ll j=1;j<=11;j++){b[j+1]+=b[j]/10;b[j]%=10;}f[1]+=b[12];}for(ll i=1;i<=n;i++){f[i+1]+=f[i]/10;f[i]%=10;}while(!f[n])n--;while(n)printf("%lld",f[n--]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的jzoj6065-[NOI2019模拟2019.3.18]One？One!【FFT】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。