模拟赛20200104 T2【杜教筛】

题目描述：

$n\le10^{10}$n≤1010

题目分析：

根据差比数列的基本操作可得：
$\sum_{i=1}^ni10^i=\frac {(9n-1)10^{n+1}+10}{81}$i=1∑n​i10i=81(9n−1)10n+1+10​
根据杜教筛的基本操作可得：
$\sum_{d=1}^nd\mu(d)=1-\sum_{i=2}^ni\sum_{d=1}^{\lfloor\frac ni\rfloor}d\mu(d)$d=1∑n​dμ(d)=1−i=2∑n​id=1∑⌊in​⌋​dμ(d)

打代码的时候发现由于n/i/j=n/(ij)等等不知名的神奇原因，杜教筛可以不用递归！

Code：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int mod = 258280327, N = 10000000, inv81 = 255091681;
LL n;
int p[N/5],sum[N+5];bool v[N+5];
map<LL,int>F;
inline int Pow(int a,LL b){int s=1;for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) s=1ll*s*a%mod;return s;}
void Prime(const int N){
    int m=0;sum[1]=1;
    for(int i=2;i<=N;i++){
        if(!v[i]) p[++m]=i,sum[i]=-i;
        for(int j=1,k;j<=m&&(k=i*p[j])<=N;j++){
            v[k]=1; if(i%p[j]==0) break;
            sum[k]=1ll*sum[i]*sum[p[j]]%mod;
        }
    }
    for(int i=1;i<=N;i++) sum[i]=(sum[i]+sum[i-1])%mod;
}
inline int calc(LL n){return ((9*n%mod-1)*Pow(10,n+1)%mod+10)*inv81%mod;}
inline int S2(LL n){n%=mod;return (n*(n+1)>>1)%mod;}
int Sum(LL n){
    if(n<=N) return sum[n];
    if(F.count(n)) return F[n];
    int ret=1;
    for(LL i=2,j,k,pre=1,now;i<=n;i=j+1,pre=now)//没有递归！！！
		j=n/(k=n/i),ret=(ret-1ll*((now=S2(j))-pre)*(k<=N?sum[k]:F[k]))%mod;
	return F[n]=ret;
}
int main()
{
    freopen("simple.in","r",stdin);
    freopen("simple.out","w",stdout);
    scanf("%lld",&n),Prime(min(1ll*N,n));
    int ans=0;
    for(LL i=1,j;i<=n;i=j+1)
        j=n/(n/i),ans=(ans+1ll*(Sum(j)-Sum(i-1))*calc(n/i))%mod;
    printf("%d\n",(ans+mod)%mod);
}