A25055. 可怜的简单题
填空题
困难
知识点
题目描述
可怜的简单题
题目描述
九条可怜今年出了一道简单题 —— 打算按照如下的方式生成一个随机的整数数列 A:
1 . 最开始，数列 A 为空。
2 . 可怜会从区间 [1,n] 中等概率随机一个整数 i 加入到数列 A 中。
3 . 如果不存在一个大于 1 的正整数 w，满足 A 中所有元素都是 w 的倍数，数组 A 将会作为随机生成的结果返回。否则，可怜将会返回第二步，继续增加 A 的长度。
现在，可怜告诉了你数列 n 的值，她希望你计算返回的数列 A 的期望长度。
输入
输入一行两个整数 n, p (1 ≤ n ≤ 1011, n < p ≤ 1012)，p 是一个质数。
输出
在一行中输出一个整数，表示答案对 p 取模的值。具体来说，假设答案的最简分数表示为 x/y，你需要输出最小的非负整数 z 满足 y × z ≡ x mod p。
样例输入
样例1：
2 998244353样例2：
100000000 998244353样例输出
样例1：
2样例2：
3054970参考答案
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Lim=2.2e7, 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;
}
上一题
下一题