80ptsWA #2#10

#include<bits/stdc++.h>
#define N 5000009
using namespace std;
int primes[N],phi[N],f[N];
#define int long long
int n,cnt,mod,inv2,inv3;
bool st[N];
int ksm(int a,int b){
	int ans=1;
	while(b){
		if(b&1){
			ans=ans*a%mod;
		}
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
void init(int n){
	phi[1]=1;
	for(int i=2;i<=n;i++){
		if(!st[i]){
			primes[++cnt]=i;
			phi[i]=i-1;
		}
		for(int j=1;primes[j]*i<=n;j++){
			st[primes[j]*i]=1;
			if(i%primes[j]==0){
				phi[primes[j]*i]=phi[i]*primes[j];
				break;
			}
			else phi[primes[j]*i]=phi[i]*(primes[j]-1);
		}
	}
	for(int i=1;i<=n;i++){
		f[i]=(f[i-1]+phi[i]*i%mod*i%mod)%mod;
	}
}
inline int g(int x,int y){
	return x/(x/y);
}
inline int gs(int n){
	return n*(n+1)%mod*inv2%mod;
}
inline int gt(int n){
	return n*(n+1)%mod*(n*2+1)%mod*inv2%mod*inv3%mod;
}
map<int,int>mp;
int sumf(int n){
	if(n<=5000000){
		return f[n];
	}
	if(mp[n]!=0){
		return mp[n];
	}
	int ans=gs(n)*gs(n)%mod,l=2,r;
	while(l<=n){
		r=g(n,l);
		ans=(ans-(gt(r)-gt(l-1))*sumf(n/l)%mod)%mod;
		l=r+1;
	}
	return mp[n]=ans;
}
int calc(int n){
	int l=1,r,ans=0;
	while(l<=n){
		r=g(n,l);
		ans=(ans+(sumf(r)-sumf(l-1))*gs(n/l)%mod*gs(n/l)%mod)%mod;
		l=r+1;
	}
	return ans;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>mod>>n;
	inv2=ksm(2,mod-2);
	inv3=ksm(3,mod-2);
	init(5000000);
	cout<<(calc(n)+mod)%mod;
	return 0;
}