本地跑数据2.276s，洛谷4s时限4.2s卡满！！！太nb了！！！！

https://www.luogu.com.cn/record/111277498

代码:

#include<bits/stdc++.h>
#include<unordered_map>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
int n,N;
int qzh[10000005];
signed mob[10000005];
signed zs[10000005];
bool flag[10000005];
gp_hash_table<long long,long long>m;
int ny6,ny4;
signed dfs(int x)
{
	if(x<=10000000)
	{
		return qzh[x]; 
	}
	if(m.find(x)!=m.end())
	{
		return m[x];
	}
	int ans=1;
	for(int i=2,j;i<=x;i=j+1)
	{
		j=(x/(x/i));
		int modi=(i-1)%N,modj=j%N;
		//i^2+...+j^2;
		ans-=((modj*(modj+1)%N*(2*modj+1)%N-modi*(modi+1)%N*(2*modi+1)%N+N)*ny6%N)*dfs(x/i)%N;
		if(ans<0)
			ans+=N;
	}
	m[x]=ans;
	return ans;
 } 
int ksm(int x,int c)
{
	if(c==0)
	{
		return 1;
	}
	if(c%2==0)
	{
		int tmp=ksm(x,c/2);
		tmp*=tmp;
		tmp%=N;
		return tmp;
	}
	else
	{
		int tmp=ksm(x,c/2);
		tmp*=tmp;
		tmp%=N;
		tmp*=x;
		tmp%=N;
		return tmp; 
	}
}
int ans,cnt,modj1,tt,modi1;
signed main()
{
	cin>>N>>n;
	//N=1000000007;
	//n=9786510294;//测速 
	const int NN=N;
	const int nn=n;
	ny6=ksm(6,NN-2);
	ny4=ksm(4,NN-2);
	mob[1]=1;
	qzh[1]=1;
	for(int i=2;i<=10000000;i++)
	{
		if(flag[i]==0)
		{
			zs[++cnt]=i;
			mob[i]=-1;
		}
		qzh[i]=qzh[i-1]+i*i*mob[i];
		qzh[i]%=NN;
		if(qzh[i]<0)
		{
			qzh[i]+=NN;
		}
		for(int j=1;j<=cnt&&1LL*i*zs[j]<=10000000;j++)
		{
			flag[i*zs[j]]=1;
			if(i%zs[j]==0)
			{
				mob[i*zs[j]]=0;
				break;
			}
			mob[i*zs[j]]=-mob[i];
		}
	}
	for(int i1=1,j1;i1<=nn;i1=j1+1)
	{
		j1=nn/(nn/i1);
		int x1=nn/i1;
		cnt=0;
		for(int i2=1,j2;i2<=x1;i2=j2+1)
		{
			j2=x1/(x1/i2);
			//cout<<":"<<i2<<" "<<j2<<endl;
			cnt+=(dfs(j2)-dfs(i2-1)+NN)*(((x1/i2+1)*(x1/i2)/2%NN)*((x1/i2+1)*(x1/i2)/2%NN)%NN)%NN;
			cnt%=NN;
		}
		//cout<<"::"<<i1<<" "<<cnt<<" "<<tt<<endl;
		modj1=j1%NN,modi1=i1%NN;
		tt=(modj1*modj1%NN*(modj1+1)%NN*(modj1+1)%NN-(modi1-1)*(modi1-1)%NN*modi1%NN*modi1%NN+NN)*ny4%NN;
		ans+=tt*cnt%NN;
		ans%=NN;	
	}
	cout<<ans<<endl;
	return 0;
}