题目

杜教筛板子了

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<tr1/unordered_map>

#define re register

#define maxn 5000005

#define LL long long

using namespace std::tr1;

unordered_map<int,int> ma;

unordered_map<int,LL> Ma;

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

inline int read()

{

    char c=getchar();

    int x=0;

    while(c<'0'||c>'9') c=getchar();

    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();

    return x;

}

int f[maxn],p[maxn>>1],mu[maxn];

LL phi[maxn];

int N[101];

int M,T;

int solve(int x)

{

    if(x<=M) return mu[x];

    if(ma.find(x)!=ma.end()) return ma[x];

    int now=1;

    for(re int l=2,r;l<=x;l=r+1)

    {

        r=x/(x/l);

        now-=(r-l+1)*solve(x/l);

    }

    return ma[x]=now;

}

LL work(int x)

{

    if(x<=M) return phi[x];

    if(Ma.find(x)!=Ma.end()) return Ma[x];

    LL ans=(LL)x*(x+1)/2;

    for(re int l=2,r;l<=x;l=r+1)

    {

        r=x/(x/l);

        ans-=(LL)(r-l+1)*work(x/l);

    }

    return Ma[x]=ans;

}

int main()

{

    T=read();

    for(re int i=1;i<=T;i++) N[i]=read(),M=max(M,N[i]);

    M=5000000;

    f[1]=mu[1]=phi[1]=1;

    for(re int i=2;i<=M;i++)

    {

        if(!f[i]) p[++p[0]]=i,mu[i]=-1,phi[i]=i-1;

        for(re int j=1;j<=p[0]&&p[j]*i<=M;j++)

        {

            f[p[j]*i]=1;

            if(i%p[j]==0)

            {

                phi[p[j]*i]=p[j]*phi[i];

                break;

            }

            mu[i*p[j]]=-1*mu[i];

            phi[i*p[j]]=phi[i]*phi[p[j]];

        }

    }

    for(re int i=1;i<=M;i++) mu[i]+=mu[i-1],phi[i]+=phi[i-1];

    for(re int t=1;t<=T;t++) printf("%lld %d\n",work(N[t]),solve(N[t]));

    return 0;

}

发现自己杜教筛常数太大了，b站卡不过去

于是怒写Min_25，发现还是卡着过的

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#define maxn 100005

#define re register

#define LL long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

inline int read() {

	int x=0;char c=getchar();while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

int T,D,a[12];

LL n,m,w[maxn],id1[maxn],id2[maxn],g[maxn],d[maxn],pre[maxn];

int f[maxn],p[maxn>>1],tot;

inline LL Sphi(LL x,int y) {

	if(x<=1||p[y]>x) return 0;

	int t=(x<=D)?id1[x]:id2[n/x];

	LL ans=d[t]-g[t]-(pre[y-1]-y+1);

	for(re int k=y;k<=tot&&p[k]*p[k]<=x;k++) {

		LL p1=p[k],now=p[k]-1;

		for(re int e=1;p1<=x;e++,p1*=p[k],now*=p[k])

			ans+=now*(Sphi(x/p1,k+1)+(e>1));

	}

	return ans;

}

inline int Smu(LL x,int y) {

	if(x<=1||p[y]>x) return 0;

	int t=(x<=D)?id1[x]:id2[n/x];

	int ans=-1*g[t]+y-1;

	for(re int k=y;k<=tot&&p[k]*p[k]<=x;k++) {

		ans-=Smu(x/p[k],k+1);

	}

	return ans;

}

int main() {

	T=read();

	for(re int i=1;i<=T;i++) a[i]=read(),D=max(D,a[i]);

	f[1]=1;D=std::sqrt(D)+1;

	for(re int i=2;i<=D;i++) {

		if(!f[i]) p[++tot]=i,pre[tot]=pre[tot-1]+i;

		for(re int j=1;j<=tot&&p[j]*i<=D;j++) {

			f[p[j]*i]=1;if(i%p[j]==0) break;

		}

	}

	for(re int tt=1;tt<=T;tt++) {

		n=a[tt];m=0;

		if(!n) {puts("0 0");continue;}

		for(re LL l=1,r;l<=n;l=r+1) {

			r=n/(n/l);w[++m]=n/l;

			if(w[m]<=D) id1[w[m]]=m;

				else id2[n/w[m]]=m;

			g[m]=w[m]-1ll;

			d[m]=(w[m]+2ll)*(w[m]-1ll);d[m]/=2ll;

		}

		for(re int j=1;j<=tot&&p[j]*p[j]<=n;j++)

			for(re int i=1;i<=m&&p[j]*p[j]<=w[i];i++) {

				int k=(w[i]/p[j]<=D)?id1[w[i]/p[j]]:id2[n/(w[i]/p[j])];

				g[i]=g[i]-g[k]+j-1;

				d[i]=d[i]-(LL)p[j]*(d[k]-pre[j-1]);

			}

		printf("%lld %d\n",Sphi(n,1)+1ll,Smu(n,1)+1ll);

	}

	return 0;

}