AcWing 3470. 可怜的简单题
原题链接
困难
作者:
sjyxgzs
,
2021-06-08 09:13:48
,
所有人可见
,
阅读 637
C++ 代码
#include<iostream>
#include<unordered_map>
using namespace std;
typedef long long ll;
const int Lim=2.2e7+10, MAXN=Lim+10;
ll n, p;
inline ll fmul(ll a,ll x) { return (__int128)a*x%p; }
inline ll fpow(ll a,ll x) { ll ans=1; for(;x;x>>=1,a=fmul(a, a) ) if(x&1) ans=fmul(ans, a); return ans; }
inline ll inv(ll a) { return fpow(a, p-2); }
ll smu[MAXN];
int prime[MAXN], cntprime;
bool nprime[MAXN];
unordered_map<ll, ll> M;
inline ll summu(ll n){
if(n<=Lim) return smu[n];
if(M.count(n)) return M[n];
for(ll r=n, l, d;r>=1; r=l-1){
d=n/r;
l=n/(d+1)+1;
if(d<=Lim||M.count(d)) continue;
ll tmp=1;
for(ll ll=2, rr, dd;ll<=d;ll=rr+1){
dd=d/ll;
rr=d/dd;
if(dd<=Lim) tmp-=fmul(rr-ll+1, smu[dd]);
else tmp-=fmul(rr-ll+1, M[dd]);
}
M[d]=(tmp%p+p)%p;
}
return M[n];
}
inline void sieve(){
smu[1]=1;
for(int i=2;i<=Lim;++i){
if(!nprime[i]) prime[++cntprime]=i, smu[i]=-1;
for(int j=1;j<=cntprime;++j)
if(i*prime[j]>Lim) break;
else if(i%prime[j]){
nprime[i*prime[j]]=1;
smu[i*prime[j]]=-smu[i];
}
else{
nprime[i*prime[j]]=1;
smu[i*prime[j]]=0;
break;
}
}
for(int i=2;i<=Lim;++i){
smu[i]+=smu[i-1];
if(smu[i]>=p) smu[i]-=p;
else if(smu[i]<0) smu[i]+=p;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>p;
sieve();
ll ans=0;
summu(n);
for(ll l=2, r, d, tmp=n%p;l<=n;l=r+1){
d=n/l;
r=n/d;
ans+=fmul( summu(r)-summu(l-1) , inv(d-tmp+p) );
}
ans=(ans%p+p)%p;
ans=( fmul(ans, n)+summu(n)+p )%p;
cout<<ans;
cout.flush();
return 0;
}
传送门:https://pintia.cn/problem-sets/994805046380707840/problems/1386335159927652366