[ICPC 2018 Shenyang Online]Convex Hull

Link

Solution

(n+1)\sum_{i=1}^n\mu^2(i)i^2-\sum_{i=1}^n\mu^2(i)i^3

Min25筛过不去……
根据\mu^2(n)=\sum_{d^2|n}\mu(d)

\begin{aligned}&\sum_{i=1}^ni^2\mu^2(i)\\=&\sum_{i=1}^ni^2\sum_{d^2|i}\mu(d)
\\=&\sum_{d}\mu(d)d^4\sum_{i=1}^{[\frac n{d^2}]}i^2\end{aligned}
\begin{aligned}&\sum_{i=1}^ni^3\mu^2(i)\\=&\sum_{i=1}^ni^3\sum_{d^2|i}\mu(d)
\\=&\sum_{d}\mu(d)d^6\sum_{i=1}^{[\frac n{d^2}]}i^3\end{aligned}

Code

const int N=1e5,XN=N+11;

long long b20=(1ll<<20)-1,P;

long long Add(long long x,long long const &y) {
    return (x+=y)>=P?x-P:x;
}

void AddBy(long long &x,long long const &y) {
    (x+=y)>=P && (x-=P);
}

long long Minus(long long x,long long const &y) {
    return (x-=y)<0?x+P:x;
}

void MinusBy(long long &x,long long const &y) {
    (x-=y)<0 && (x+=P);
}

long long Mul(long long const &x,long long const &y,long long P=::P) {
    return ((((((x>>20)*(y>>20)<<20)+(x>>20)*(y&b20)+(y>>20)*(x&b20))%P)<<20)+(x&b20)*(y&b20))%P;
}

void MulBy(long long &x,long long const &y) {
    x=Mul(x,y);
}

int prime[XN],pcnt,mu[XN];
void Prep() {
    mu[1]=1;
    static bool notPrime[XN];
    for(int i=2;i<=N;++i) {
        if(!notPrime[i]) {
            prime[++pcnt]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=pcnt && i*prime[j]<=N;++j) {
            notPrime[i*prime[j]]=1;
            if(i%prime[j]==0) {
                mu[i*prime[j]]=0;
                break;
            } else
                mu[i*prime[j]]=-mu[i];
        }
    }
}

long long Sum2(long long x) {
    return Mul(Mul(x,x+1,P*6),x*2+1,P*6)/6;
}

long long Sum3(long long x) {
    x=Mul(x,x+1,P*2)/2;
    return Mul(x,x);
}

int main() {
    Prep();
    long long n;
    while(std::cin>>n>>P) {
        long long Ans,a=0,b=0;
        for(long long d=1;d*d<=n;++d)
            if(mu[d]) {
                long long sqd=d*d%P,tbd=sqd*d%P;
                AddBy(a,Mul(mu[d]==1?mu[d]:P-1,Mul(Mul(sqd,sqd),Sum2(n/(d*d)))));
                AddBy(b,Mul(mu[d]==1?mu[d]:P-1,Mul(Mul(tbd,tbd),Sum3(n/(d*d)))));
            }
        Ans=Minus(Mul(n+1,a),b);
        fout<<Ans<<'\n';
    }
    return 0;
}

Code(TLE)

const int N=1e5,XN=N+11;

long long b20=(1ll<<20)-1,P;

long long Add(long long x,long long const &y) {
    return (x+=y)>=P?x-P:x;
}

void AddBy(long long &x,long long const &y) {
    (x+=y)>=P && (x-=P);
}

long long Minus(long long x,long long const &y) {
    return (x-=y)<0?x+P:x;
}

void MinusBy(long long &x,long long const &y) {
    (x-=y)<0 && (x+=P);
}

long long Mul(long long const &x,long long const &y,long long P=::P) {
    return ((((((x>>20)*(y>>20)<<20)+(x>>20)*(y&b20)+(y>>20)*(x&b20))%P)<<20)+(x&b20)*(y&b20))%P;
}

void MulBy(long long &x,long long const &y) {
    x=Mul(x,y);
}

int prime[XN*2],pcnt;
void Prep() {
    static bool notPrime[XN*2];
    for(int i=2;i<=N*2;++i) {
        if(!notPrime[i])
            prime[++pcnt]=i;
        for(int j=1;j<=pcnt && i*prime[j]<=N*2;++j) {
            notPrime[i*prime[j]]=1;
            if(i%prime[j]==0)
                break;
        }
    }
}

namespace Min25 {
    std::function<long long(int,int)> F;

    long long n;
    int lim,psz;

    struct Identifier {
        int id[2][XN],cnt;
        int &operator [](long long x) {
            int &res=x<=lim?id[0][x]:id[1][n/x];
            if(res==0)
                res=++cnt;
            return res;
        }
    }id;

    long long g[XN*2],fps[XN];

    long long H(long long n,int m) {
        if(n<=1 || m>psz)
            return 0;
        long long res=Minus(g[id[n]],fps[m-1]);
        for(int i=m;i<=psz && (long long)prime[i]*prime[i]<=n;++i) {
            long long pt=prime[i],pt1=pt*prime[i];
            for(int t=1;pt1<=n;++t,pt=pt1,pt1*=prime[i])
                AddBy(res,Add(Mul(F(prime[i],t),H(n/pt,i+1)),F(prime[i],t+1)));
        }
        return res;
    }

    long long Solve(long long n,std::function<long long(int,int)> F,std::function<long long(long long)> gInit) {
        static long long kp[XN*2];
        int kpc=0;
        lim=sqrt(n)+0.5,psz=std::upper_bound(prime+1,prime+1+pcnt,lim)-prime;
        for(int i=id.cnt=0;i<=lim;++i)
            id.id[0][i]=id.id[1][i]=0;
        Min25::F=F;
        Min25::n=n;
        for(long long l=1,r;l<=n;l=r+1) {
            r=n/(n/l);
            g[id[kp[++kpc]=n/l]]=gInit(n/l);
        }
        for(int i=1;i<=psz;++i)
            fps[i]=Add(fps[i-1],F(prime[i],1));
        for(int j=1;j<=psz;++j)
            for(int i=1;i<=kpc && (long long)prime[j]*prime[j]<=kp[i];++i)
                MinusBy(g[id[kp[i]]],Mul(F(prime[j],1),Minus(g[id[kp[i]/prime[j]]],fps[j-1])));//XXX
        return H(n,1);
    }
}

long long Sum2(long long x) {
    return Mul(Mul(x,x+1,P*6),x*2+1,P*6)/6;
}

long long Sum3(long long x) {
    x=Mul(x,x+1,P*2)/2;
    return Mul(x,x);
}

int main() {
    Prep();
    long long n;
    while(std::cin>>n>>P) {
        //(n+1)*mu^2(i)*i^2-mu^2(i)*i^3
        long long a=Add(1,Min25::Solve(n,[](int p,int t)->long long { return t==1?Mul(p,p):0; },
                                         [](long long x)->long long { return Minus(Sum2(x),1);})),
                  b=Add(1,Min25::Solve(n,[](int p,int t)->long long { return t==1?Mul(p,Mul(p,p)):0; },
                                         [](long long x)->long long { return Minus(Sum3(x),1);})),
                  Ans=Minus(Mul(n+1,a),b);
        fout<<Ans<<'\n';
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注