結果

問題 No.2972 確率的素数判定
コンテスト
ユーザー Tatsu_mr
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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";
    }
}
0