Description：

给出 $s_0$ ，用如下方式生成数列 $d_i$ ： $$ d_i=\lfloor\frac{s_i}{1024}\rfloor\bmod 10，s_i=(747796405s_{i-1}-1403630843) $$ 设 $n$ 的十进制表示为 $d_0,$ $d_1,\dots,d_{l-1},d_l$ ， $oneness(k)$ 表示 $k$ 的所有大于 $1$ 的约数中十进制下全是 $1$ 的约数个数，给出 $l$ ，求： $$ \sum_{i=1}^noneness(i) $$ $1\leqslant l\leqslant 250000$

Solution：

$$ \sum_{i=1}^noneness(i)=\sum_{i=2}^l\bigg\lfloor\frac n{\underbrace{11\cdots 1}_{i个1}}\bigg\rfloor=\sum_{i=2}^l\bigg\lfloor\frac{9n}{10^l-1}\bigg\rfloor $$

设 $N=9n=x\times 10^d+y(y<10^d)$ ，那么： $$ \bigg\lfloor\frac N{10^l-1}\bigg\rfloor=\bigg\lfloor\frac {x\times 10^l}{10^l-1}+\frac y{10^l-1}\bigg\rfloor=\bigg\lfloor\frac{x\times (10^l-1)+x}{10^l-1}+\frac y{10^l-1}\bigg\rfloor=\bigg\lfloor x+\frac x{10^l-1}+\frac y{10^l-1}\bigg\rfloor $$ 然后我们考虑计算贡献，会发现每次相当于是把 $N$ 十进制下右移了 $l$ 位再计算，我们先只考虑 $x$ 那部分贡献，那么也就是第 $i$ 位对第 $j$ 位的贡献是 $i-j$ 不为 $1$ 的约数个数，也就是 $b[j]=\sum_{i=j}^na[i]\times (\sigma(i-j)-1)$ 这其实是一个卷积，可以用 $FFT$ 加速计算。

最后考虑 $y$ 的贡献，会发现其实是把 $N$ 每 $l$ 分一段加在一起，因为最后有一个下取整而且数据近似随机，我们可以只把高 $15$ 位拿出来暴力计算。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n;

#define MAXN 1000010

unsigned int s[MAXN];

int d[MAXN];

int v1[MAXN];

int sigma[MAXN];

int res[MAXN];

int ans[MAXN];

int ww[MAXN << 1],*g = ww + MAXN;

int rev[MAXN];

#define P 998244353

int power(int a,int b)

{

	int res = 1;

	for(;b > 0;b = b >> 1,a = 1ll * a * a % P)if(b & 1)res = 1ll * res * a % P;

	return res;

}

int init(int n)

{

	int l = 0,len = 1;

	for(;len <= n;len = len << 1)++l;

	for(int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

	g[0] = g[-len] = 1;g[1] = g[1 - len] = power(3,(P - 1) / len);

	for(int i = 2;i < len;++i)g[i] = g[i - len] = 1ll * g[i - 1] * g[1] % P;

	return len;

}

void NTT(int f[],int l,int type)

{

	for(int i = 0;i < l;++i)

	{

		if(i < rev[i])swap(f[i],f[rev[i]]);

	}

	for(int i = 2;i <= l;i = i << 1)

	{

		int wn = g[type * l / i];

		for(int j = 0;j < l;j += i)

		{

			int w = 1;

			for(int k = j;k < j + i / 2;++k)

			{

				int u = f[k],t = 1ll * w * f[k + i / 2] % P;

				f[k] = (u + t) % P;

				f[k + i / 2] = (u - t + P) % P;

				w = 1ll * w * wn % P;

			}

		}

	}

	if(type == -1)

	{

		int ni = power(l,P - 2);

		for(int i = 0;i < l;++i)f[i] = 1ll * f[i] * ni % P;

	}

	return;

}

int t[MAXN];

#define L 15

long long pow10[20];

int main()

{

	scanf("%d",&n);

	scanf("%d",&s[0]);

	for(int i = 1;i <= n;++i)s[i] = (747796405ll * s[i - 1] - 1403630843) % (1ll << 32);

	for(int i = 0;i < n;++i)d[i] = (s[i] / 1024) % 10;

	for(int i = n;i >= 1;--i)d[i] = d[i - 1];

	for(int i = 1,j = n;i < j;++i,--j)swap(d[i],d[j]);

	d[0] = 0;

	for(int i = n;i >= 1;--i)d[i] = d[i] * 9;

	for(int i = 1;i <= n;++i)d[i + 1] += d[i] / 10,d[i] %= 10;

	if(d[n + 1])++n;

	for(int i = 2;i <= n;++i)for(int j = i;j <= n;j += i)++sigma[j];

	sigma[0] = 1;

	for(int i = 0;i <= n;++i)v1[i] = d[i];

	for(int i = 0,j = n;i < j;++i,--j)swap(v1[i],v1[j]);

	int l = init(n * 2);

	NTT(sigma,l,1);NTT(v1,l,1);

	for(int i = 0;i < l;++i)t[i] = 1ll * sigma[i] * v1[i] % P;

	NTT(sigma,l,-1);NTT(v1,l,-1);NTT(t,l,-1);

	for(int k = 1;k <= n - 2;++k)res[k] += t[n - k];

	for(int k = 1;k <= n - 2;++k)res[k] -= d[k];

	int cur = 100;

	pow10[0] = 1;

	for(int i = 1;i <= L;++i)pow10[i] = 1ll * pow10[i - 1] * 10;

	for(int i = 2;i <= n;++i)

	{

		int l = min(L,i);

		long long ss = 0;

		for(int k = i;k < n + i;k += i)for(int j = 1;j <= l;++j)ss += 1ll * d[k - j + 1] * pow10[l - j];

		res[1] += ss / (pow10[l] - 1);

		cur = cur * 10;

	}

	for(int i = 1;i <= n;++i)

	{

		int val = res[i];

		if(val < 0)

		{

			val = -val;

			int cnt = val / 10;

			res[i + 1] -= val;

			res[i] += val * 10;

			while(res[i] < 0)res[i] += 10,res[i + 1]--;

		}

	}

	for(int i = 1;i <= n;++i)res[i + 1] += res[i] / 10,res[i] %= 10;

	while(res[n + 1])++n,res[n + 1] += res[n] / 10,res[n] %= 10;

	while(res[n] == 0)--n;

	for(int i = n;i >= 1;--i)cout << res[i];cout << endl;

	return 0;

}