题目大意

CJY很喜欢吃蛋糕，于是YJC弄到了一块蛋糕，现在YJC决定和CJY分享蛋糕。
这块蛋糕上有n^2颗葡萄干，排成了一个n*n的点阵，每颗葡萄干互不相同且被编号为1~n^2。YJC决定沿着一条直线把蛋糕切成两份。YJC和CJY都很喜欢吃葡萄干，所以切出的两份蛋糕必须都包含至少一颗葡萄干。同时他们都不希望吃到不完整的葡萄干，所以切的时候不能经过任意一颗葡萄干。CJY喜欢1号葡萄干，所以他选择了包含1号葡萄干的那块蛋糕，而YJC则选择了另一块。
在吃蛋糕之前,CJY想知道有多少种切蛋糕的方案。两种方案是不同的当且仅当存在一颗葡萄干在一种方案中被分给了CJY，在另一种方案中被分给了YJC。CJY发现自己不会做这道题，所以他来向你请教。这个答案可能很大，你只需要告诉他答案mod p的结果就可以了。

筛

不会推结论
抄了std的式子
然后杜教筛啊

#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int maxn=1000000+10;
ll sum[maxn][3],gg[maxn][3];
int phi[maxn],pri[maxn];
bool bz[maxn];
int i,j,k,l,t,n,m,top,mo,ans;
void prepare(){phi[1]=1;fo(i,2,maxn-10){if (!bz[i]) pri[++top]=i,phi[i]=i-1;fo(j,1,top){if ((ll)i*pri[j]>maxn-10) break;bz[i*pri[j]]=1;if (i%pri[j]==0){phi[i*pri[j]]=phi[i]*pri[j];break;}phi[i*pri[j]]=phi[i]*(pri[j]-1);}}fo(i,1,maxn-10){sum[i][0]=(sum[i-1][0]+phi[i])%mo;sum[i][1]=(sum[i-1][1]+(ll)phi[i]*i%mo)%mo;sum[i][2]=(sum[i-1][2]+(ll)phi[i]*i%mo*i%mo)%mo;}
}
int getsum(int n,int k){int a,b,c;if (!k) return n;else if (k==1) return ((ll)n*(n+1)/2)%mo;else if (k==2){a=n;b=n+1;c=2*n+1;if (a%2==0) a/=2;else b/=2;if (a%3==0) a/=3;else if (b%3==0) b/=3;else c/=3;return (ll)a*b%mo*c%mo;}else{a=((ll)n*(n+1)/2)%mo;return (ll)a*a%mo;}
}
int calc(int n,int k){if (n<=maxn-10) return sum[n][k];if (gg[m/n][k]) return gg[m/n][k];int i=2,j,t,s0,s1,s2;s0=getsum(n,1);s1=getsum(n,2);s2=getsum(n,3);while (i<=n){j=n/(n/i);t=(getsum(j,0)-getsum(i-1,0))%mo;(s0-=(ll)t*calc(n/i,0)%mo)%=mo;t=(getsum(j,1)-getsum(i-1,1))%mo;(s1-=(ll)t*calc(n/i,1)%mo)%=mo;t=(getsum(j,2)-getsum(i-1,2))%mo;(s2-=(ll)t*calc(n/i,2)%mo)%=mo;i=j+1;}gg[m/n][0]=s0;gg[m/n][1]=s1;gg[m/n][2]=s2;return gg[m/n][k];
}
int main(){freopen("cake.in","r",stdin);freopen("cake.out","w",stdout);scanf("%d%d",&n,&mo);m=n;prepare();ans=(ll)n*n%mo*2%mo*calc(n,0)%mo;(ans-=(ll)3*n%mo*calc(n,1)%mo)%=mo;(ans+=calc(n,2))%=mo;ans=ans*2%mo;(ans+=mo)%=mo;printf("%d\n",ans);
}