正题
题目链接:https://gmoj.net/senior/#main/show/6065
题目大意
o n e n e s s ( x ) oneness(x) oneness(x)体现 x x x的约数中全是 1 1 1的数的个数，给出一个长度为 l l l的随机生成的数 n n n，求 ∑ i = 1 n o n e n e s s ( i ) \sum_{i=1}^noneness(i) i=1∑noneness(i)
解题思路
转换一下题意就是求 ∑ i = 2 l ⌊ n 1 0 i − 1 9 ⌋ = ∑ i = 2 l ⌊ 9 n 1 0 i − 1 ⌋ \sum_{i=2}^l\lfloor\frac{n}{\frac{10^i-1}{9}}\rfloor=\sum_{i=2}^l\lfloor\frac{9n}{10^i-1}\rfloor i=2∑l⌊910i−1n⌋=i=2∑l⌊10i−19n⌋
先让 n n n乘上 9 9 9，然后把每一位的贡献拆成小数和整数部门，我们先来看整数部门
首先对于一个 k ∗ 1 0 i 1 0 j − 1 \frac{k*10^i}{10^j-1} 10j−1k∗10i那么它的值应该是在第 i − x j + 1 ( x ∈ N ) i-xj+1(x\in N) i−xj+1(x∈N)位会有一个 k k k。（如 1 0 9 999 = 1001001.001001001001001001001001 \frac{10^9}{999}=1001001.001001001001001001001001 999109=1001001.001001001001001001001001）
然后我们看这题， j j j是 1 ∼ n 1\sim n 1∼n的每一个值，那么对于每第 i i i位我们拆成 k ∗ 1 0 i k*10^i k∗10i会对第 i − x i-x i−x位产生 σ 0 ( x ) \sigma_0(x) σ0(x)次贡献（ σ 0 ( x ) \sigma_0(x) σ0(x)体现 x x x的约数个数）。设 a i a_i ai体现第 i i i位的数， f i f_i fi体现第 i i i位的答案，那么有式子 f i = ∑ j = 0 ∞ a i + j σ 0 ( j ) f_i=\sum_{j=0}^{\infty}a_{i+j}\sigma_0(j) fi=j=0∑∞ai+jσ0(j)
这个式子可以先预处置惩罚出 σ 0 ( j ) \sigma_0(j) σ0(j)然后把 a a a反过来就是一个卷积的式子， F F T FFT FFT优化即可。
对于小数部门，因为在比力后的位数的产生贡献概率极小，又因为数字随机生成，所以我们直接将这些部门省略。我们只处置惩罚到小数的 12 12 12位，和上面同理算出每一个小数位的贡献即可。
时间复杂度 O ( n log n ) O(n\log n) O(nlogn)
c o d e code code
[code]#include#include#include#include#include#define ll long longusing 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 |
