不会......
两篇加在一起都看不懂......
- //minamoto
- #include<iostream>
- #include<cstdio>
- #include<map>
- #define ll long long
- using namespace std;
- const int N=4e6+5;
- map<ll,ll> mp;
- ll sum[N],phi[N],pri[N],cnt,vis[N],mod6,mod;
- //mod 是 2 的逆元, mod6 是 6 的逆元
- void init(ll p){
- vis[1]=sum[1]=1;
- for(int i=2;i<N;++i){
- if(!vis[i]) pri[++cnt]=i,phi[i]=i-1,sum[i]=1ll*i*i%p*phi[i]%p;
- for(int j=1;j<=cnt,i*pri[j]<N;++j){
- vis[i*pri[j]]=1;
- int now=i*pri[j];
- if(i%pri[j]==0){
- phi[now]=phi[i]*pri[j]%p;
- sum[now]=phi[now]*now%p*now%p;
- break;
- }
- phi[now]=phi[i]*(pri[j]-1)%p;
- sum[now]=phi[now]*now%p*now%p;
- }
- }
- for(int i=2;i<N;++i) (sum[i]+=sum[i-1])%=p;
- }
- ll ksm(ll x,ll y,ll p){
- ll res=1;
- while(y){
- if(y&1) (res*=x)%=p;
- (x*=x)%=p,y>>=1;
- }
- return res;
- }
- ll calc(ll n,ll p){
- n%=p;
- ll res=((1+n)*n%p)*mod%p;
- (res*=res)%=p;
- return res;
- }
- ll calcs(ll n,ll p){
- n%=p;
- ll res=(n*(n+1)%p)*(2*n+1)%p;
- (res*=mod6)%=p;
- return res;
- }
- ll calcsum(ll n,ll p){
- if(n<N) return sum[n];
- if(mp.count(n)) return mp[n];
- ll x=2,res=calc(n,p);
- while(x<=n){
- ll y=n/(n/x);
- res=((res-(calcs(y,p)-calcs(x-1,p)+p)%p*calcsum(n/x,p)%p)+p)%p;
- x=y+1;
- }
- return mp[n]=res;
- }
- int main(){
- // freopen("testdata.in","r",stdin);
- ll p,n;
- scanf("%lld%lld",&p,&n);
- mod=ksm(2,p-2,p),mod6=ksm(6,p-2,p);
- init(p);
- ll x=1,ans=0;
- while(x<=n){
- ll y=n/(n/x);
- (ans+=((calcsum(y,p)-calcsum(x-1,p)+p)%p*calc(n/x,p)%p))%=p;
- x=y+1;
- }
- printf("%lld\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2781402.html