首页 › 题库 › C/C++编程考级 › C/C++编程八级 › 简答题
简答题 偏难
#7578

可怜的简单题 九条可怜今年出了一道简单题 —— 打算按照如下的方式生成一个随机的整数数列 A: 1 . 最开始,数列 A 为空。 2 . 可怜会从区间 [1,n…

可怜的简单题

九条可怜今年出了一道简单题 —— 打算按照如下的方式生成一个随机的整数数列 A:

1 . 最开始,数列 A 为空。

2 . 可怜会从区间 [1,n] 中等概率随机一个整数 i 加入到数列 A 中。

3 . 如果不存在一个大于 1 的正整数 w,满足 A 中所有元素都是 w 的倍数,数组 A 将会作为随机生成的结果返回。否则,可怜将会返回第二步,继续增加 A 的长度。

现在,可怜告诉了你数列 n 的值,她希望你计算返回的数列 A 的期望长度。

时间限制:60000

内存限制:1048576

输入

输入一行两个整数 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
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; 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&gt;&gt;=1,a=fmul(a, a) ) if(x&amp;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&lt;ll, ll&gt;  M; inline ll summu(ll n){     if(n&lt;=Lim) return smu[n];     if(M.count(n)) return M[n];     for(ll r=n, l, d;r&gt;=1; r=l-1){         d=n/r;         l=n/(d+1)+1;         if(d&lt;=Lim||M.count(d)) continue;         ll tmp=1;         for(ll ll=2, rr, dd;ll&lt;=d;ll=rr+1){             dd=d/ll;             rr=d/dd;             if(dd&lt;=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&lt;=Lim;++i){         if(!nprime[i]) prime[++cntprime]=i, smu[i]=-1;         for(int j=1;j&lt;=cntprime;++j)             if(i*prime[j]&gt;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&lt;=Lim;++i){         smu[i]+=smu[i-1];         if(smu[i]&gt;=p) smu[i]-=p;         else if(smu[i]&lt;0) smu[i]+=p;     } } int main(){     ios::sync_with_stdio(0);     cin.tie(0); cout.tie(0);     cin&gt;&gt;n&gt;&gt;p;     sieve();     ll ans=0;     summu(n);     for(ll l=2, r, d, tmp=n%p;l&lt;=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&lt;&lt;ans;     cout.flush();     return 0; }</pre>
这道题暂未补解析。