結果

問題 No.3187 Mingle
コンテスト
ユーザー 沙耶花
提出日時 2025-06-20 21:47:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 769 ms / 2,500 ms
コード長 790 bytes
コンパイル時間 3,884 ms
コンパイル使用メモリ 255,908 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-20 21:48:18
合計ジャッジ時間 20,319 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
using mint = modint;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000005
#define Inf64 4000000000000000001LL

int main(){
	
	int N,P;
	cin>>N>>P;
	mint::set_mod(P);
	vector<mint> dp(N+1);
	mint sum = 0;
	for(int i=3;i<=N;i++){
		mint ts = 0;
		int tc = 0;
		vector<int> ys;
		for(int j=1;j*j<=i;j++){
			if(i%j==0){
				ys.push_back(j);
				if(j != i/j) ys.push_back(i/j);
			}
		}
		ts =sum;
		rep(j,ys.size()){
			ts -= dp[ys[j]];
		}
		mint tdp = ts *mint(i - ys.size()).inv();
		mint tp = i-ys.size();
		tp /= i;
		tdp += tp.inv();
		rep(j,ys.size()){
			sum -= dp[ys[j]];
			dp[ys[j]] = tdp;
			sum += tdp;
		}
	}
	cout<<dp[N].val()<<endl;
	return 0;
}
0