結果
問題 |
No.2972 確率的素数判定
|
ユーザー |
![]() |
提出日時 | 2025-03-03 23:20:13 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 72 ms / 2,000 ms |
コード長 | 2,627 bytes |
コンパイル時間 | 4,112 ms |
コンパイル使用メモリ | 283,872 KB |
実行使用メモリ | 8,608 KB |
最終ジャッジ日時 | 2025-03-03 23:20:21 |
合計ジャッジ時間 | 7,882 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define For(i, a, b) for(int i = (a); i < (b); i++) #define rep(i, n) For(i, 0, n) #define rFor(i, a, b) for(int i = (a); i >= (b); i--) #define ALL(v) (v).begin(), (v).end() #define rALL(v) (v).rbegin(), (v).rend() using lint = long long; using ld = long double; int INF = 2000000000; lint LINF = 1000000000000000000; struct SetupIo { SetupIo() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); } } setupio; struct Sieve { private: int n; vector<int> IdxtoVal, ValtoIdx; vector<bool> deleted; void build() { int sz = (n % 30 == 0 ? n / 30 : n / 30 + 1); sz *= 8; IdxtoVal = {1, 7, 11, 13, 17, 19, 23, 29}; for (int i = 0; i < 8; i++) { ValtoIdx[IdxtoVal[i]] = i; } deleted.assign(sz, false); for (int i = 1; i < sz; i++) { if (deleted[i]) { continue; } int p = getval(i); for (int j = i; j < sz; j++) { int q = getval(j); if (q > n / p) { break; } deleted[getidx(p * q)] = true; } } } int getval(int i) { return i / 8 * 30 + IdxtoVal[i % 8]; } int getidx(int x) { return x / 30 * 8 + ValtoIdx[x % 30]; } public: Sieve(int n_) : n(n_), IdxtoVal(8), ValtoIdx(30) { build(); } bool isprime(int x) { if (x == 1) { return false; } else if (x == 2 || x == 3 || x == 5) { return true; } else if (x % 2 == 0 || x % 3 == 0 || x % 5 == 0) { return false; } else { return !deleted[getidx(x)]; } } template <class T = int> vector<T> primes() { vector<T> res; for (T i = 2; i <= T(n); i++) { if (isprime(i)) { res.emplace_back(i); } } return res; } }; const int mx = 100010; int main() { Sieve sieve(mx); vector<int> cnt(mx, 0); rep(i, mx) { if (sieve.isprime(i)) { cnt[i] = 1; } } rep(i, mx - 1) { cnt[i + 1] += cnt[i]; } int t; cin >> t; while (t--) { int n, p, q; cin >> n >> p >> q; int prime = cnt[n]; ld yes1 = ld(p) * ld(prime) / ld(100) / ld(n); ld yes2 = ld(100 - q) * ld(n - prime) / ld(100) / ld(n); ld ans = yes1 / (yes1 + yes2); cout << ans << "\n"; } }