设 $f(n) = \mu(n)n^2$，$g(n) = n^2$。

现在求 $S(n) = \sum\limits_{i = 1}^n f(i)$。

容易得到 $(f*g)(n) = \sum\limits_{d|n}\mu(d)d^2\frac{n^2}{d^2} =n^2 \sum\limits_{d|n}\mu(d) = n^2$。

注意到 $g(n)$，$(f*g)(n)$ 都可以 $O(1)$ 前缀和，以此执行杜教筛。

然而交上去 TLE 了，我本地测试发现是杜教筛跑的巨慢，然而我没发现和我之前写的有啥区别。

求助大佬们 /bx.

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
ll mod;
const int maxn=4641588+5;
bitset<maxn> nop;
ll mu[maxn];// mu * pos^2
vi prime;
cc_hash_table<ll,ll> rem;
ll pw2pre(__int128 n){
    __int128 res= n*(n+1)*(2*n+1);
    res%=mod;
    return res*res%mod;
}
ll pw2(ll l,ll r){
    return pw2pre(r)-pw2pre(l-1);
}
ll mupre(ll n){
    if(n<maxn)return mu[n];
    if(rem.find(n)!=rem.end()){
        return rem[n];
    }
    ll ans=1;// 另一个工具函数是 p(i) = i^2
    for(ll l=2,r;l<=n;l=r+1){
        r=n/(n/l);
        ans-=pw2(l,r)%mod*mupre(n/l)%mod;
    }
    ans%=mod;
    return rem[n]=ans;
}
ll pw3pre(__int128 n){
    // 1^3+2^3+...+n^3
    __int128 res=(n*(n+1)/2);
    res%=mod;
    return (res*res)%mod;    
}
ll pw3(ll l,ll r){
    return pw3pre(r)-pw3pre(l-1);
}
ll s(__int128 n){
	__int128 ans=(1+n)*n/2ll;
	ans%=mod;
	return ans*ans%mod;
}
ll g(ll n){
    ll ans=0;
    for(ll l=1,r;l<=n;l=r+1){
        r=n/(n/l);
	//	printf("g l = %lld r = %lld\n",l,r);
        ans+=(mupre(r)-mupre(l-1))*s(n/l)%mod;
        ans%=mod;
    }
    return ans;
}
ll n;
void solve(int id_of_test){
	read(n);
    ll ans=0;
    for(ll l=1,r;l<=n;l=r+1){
        r=n/(n/l);
	//	printf("l %lld r %lld\n",l,r);
        ans+=(pw3(l,r)*g(n/l))%mod;
        ans%=mod;
	}
    printf("%lld\n",(ans+mod)%mod);
}
int main()
{
    read(mod);
	int T;
	T=1;
    nop[1]=1;
    mu[1]=1;
    FOR(i,2,maxn-1){
        if(!nop[i]){
            prime.eb(i);
            mu[i]=-1;
        }
        for(int& v:prime){
            if(i*v>=maxn)break;
            nop[i*v]=1;
            if(i%v==0){
                break;
            }
            mu[i*v]=-mu[i];
        }
    }
    FOR(i,1,maxn-1){
        mu[i]=mu[i]*i%mod*i%mod;
        mu[i]+=mu[i-1];
        mu[i]%=mod;
    }
	//printf("mupre %lld\n",mupre(ll(1e10)));
//	mt19937 rnd({random_device{}()});
//	FOR(_,1,1000){
//		ll tmp=rnd()%(ll(1e10))+1;
//		printf("mupre %lld = %lld\n",tmp,mupre(tmp));
//	}
	FOR(_,1,T){
		solve(_);
	}
	return 0;
}