結果

問題 No.3187 Mingle
ユーザー pockyny
提出日時 2025-07-07 00:29:33
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 700 ms / 2,500 ms
コード長 1,683 bytes
コンパイル時間 1,212 ms
コンパイル使用メモリ 81,832 KB
実行使用メモリ 39,372 KB
最終ジャッジ日時 2025-07-07 00:30:06
合計ジャッジ時間 20,059 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <atcoder/modint>

using namespace std;
using namespace atcoder;
using mint = modint;
typedef long long ll;
ll INF = 1000000000000000000;
template<typename T = ll>
struct segment_tree{
    int n; vector<T> seg;
    T e(){return 0;}
    T op(T a,T b){return (a + b);}
    segment_tree(){}
    segment_tree(int sz){n = sz; seg.resize(2*n,e());}
    segment_tree(vector<T> v){
        n = v.size(); seg.resize(2*n,e());
        for(int i=0;i<n;i++) seg[i + n] = v[i];
        for(int i=n - 1;i>0;i--) seg[i] = op(seg[i<<1],seg[i<<1|1]);
    }
    void init(int sz){n = sz; seg.resize(2*n);}
    void update(int p,T val){
        for(seg[p += n] = val;p>1;p>>=1) seg[p>>1] = op(seg[p],seg[p^1]);
    }
    T get(int p){return seg[p + n];}
    T query(int l,int r){
        T res = e();
        for(l += n,r += n; l<r;l>>=1,r>>=1){
            if(l&1) res = op(res,seg[l++]);
            if(r&1) res = op(res,seg[--r]);
        }
        return res;
    }
    void clear(){for(int i=0;i<2*n;i++) seg[i] = e();}
};

const int MX = 300000;
vector<int> di[MX + 10];
mint p[MX + 10];
int main(){
    int i,j,n,P; cin >> n >> P;
    mint::set_mod(P);
    for(i=1;i<=MX;i++){
        for(j=i;j<=MX;j+=i) di[j].push_back(i);
    }
    segment_tree<mint> seg(MX + 1);
    p[n] = 1;
    seg.update(n,p[n]/(mint)(n - di[n].size()));
    for(i=n - 1;i>=3;i--){
        for(int x:di[i]){
            p[i] += seg.query(i + 1,min(x + i,MX + 1));
        }
        if(i>2) seg.update(i,p[i]/(mint)(i - di[i].size()));
    }
    mint ans = 0;
    for(i=3;i<=n;i++){
        ans += p[i]/(1 - (mint)di[i].size()/(mint)i);
    }
    cout << ans.val() << "\n";
}
0