ferinの競プロ帳

競プロについてのメモ

2020 Petrozavodsk Winter Camp, Jagiellonian U Contest A問題 Bags of Candies

codeforces

問題ページ

概要

$1 \sim N$ の $N$ 種類の味のキャンディがある
バッグに1か2種類を入れる
ただし2種類の場合、味の $\text{gcd}$ が2以上でなければならない
バッグの数を最小化しろ
$N \leq 10^{11}$

解法

2種類のペアをつくる数を最大化すればバッグの数を最小化できる。味1のキャンディと $N/2$ より大きいの素数の味のキャンディをペアの片方にすることは不可能である。これらの味の集合を $D$ とすると、ペアの個数は $\lfloor \frac{N-|D|}{2} \rfloor$ 以下である。

この上限を必ず達成できることを示す。 $f(x)=(x$ の素因数のうち最大のもの $)$ とする。 $D$ に属さない味のうち、 $f(x)$ が同じ味のものをまとめた集合を考える。要素数が偶数の集合についてはこれらの集合内でペアをつくればよい。要素数が奇数の集合については $2f(x)$ 以外の要素でペアをつくり、余った $2f(x)$ については別の集合同士でペアをつくればよい。したがって、 $D$ に属さない味のキャンディでペアを構成することは常に可能である。

あとは $N/2$ より大きい素数の個数を高速に求められれば良い。Counting Primes の高速な提出を写経するとこれはできる。

想定解に $10^7$ ごとに素数の数を数えておいて埋め込めばよいと書かれていたので計算したらこどふぉのファイル長の制限に引っかかったの何？

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for(ll i=(ll)a; i<(ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG  
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
constexpr ll INF = 1LL<<60;  
  
// N以下の素数の数を数える  
// https://judge.yosupo.jp/submission/7976 の写経でN<=10^11 が25ms  
__attribute__((target("avx"), optimize("O3", "unroll-loops")))  
ll prime_count(const ll N) {  
    if(N <= 1) return 0;  
    if(N == 2) return 1;  
    const int v = sqrtl(N);  
    int s = (v+1)/2;  
    vector<int> smalls(s), roughs(s);   
    for(int i=1; i<s; ++i) smalls[i] = i;  
    for(int i=0; i<s; ++i) roughs[i] = 2*i+1;  
    vector<ll> larges(s);   
    for(int i=0; i<s; ++i) larges[i] = (N/(2*i+1)-1)/2;  
    vector<bool> skip(v+1);  
    const auto divide = [](ll n, ll d) -> int { return double(n) / d; };  
    const auto half = [](int n) -> int { return (n - 1) >> 1; };  
    int pc = 0;  
    for(int p=3; p<=v; p+=2) if(!skip[p]) {  
        int q = p*p;  
        if (ll(q)*q > N) break;  
        skip[p] = true;  
        for(int i=q; i<=v; i+=2*p) skip[i] = true;  
        int ns=0;  
        for(int k=0; k<s; ++k) {  
            int i = roughs[k];  
            if(skip[i]) continue;  
            ll d = ll(i) * p;  
            larges[ns] = larges[k] - (d<=v ? larges[smalls[d>>1]-pc] : smalls[half(divide(N, d))]) + pc;  
            roughs[ns++] = i;  
        }  
        s = ns;  
        for(int i=half(v), j=((v/p)-1)|1; j>=p; j-=2) {  
            int c = smalls[j>>1]-pc;  
            for(int e=(j*p)>>1; i>=e; --i) smalls[i] -= c;  
        }  
        ++pc;  
    }  
    larges[0] += ll(s+2*(pc-1))*(s-1)/2;  
    for(int k=1; k<s; ++k) larges[0] -= larges[k];  
    for(int l=1; l<s; ++l) {  
        int q = roughs[l];  
        ll M = N/q;  
        int e = smalls[half(M / q)]-pc;  
        if(e<l+1) break;  
        ll t = 0;  
        for(int k = l + 1; k <= e; ++k) t += smalls[half(divide(M, roughs[k]))];  
        larges[0] += t-ll(e-l)*(pc+l-1);  
    }  
    return larges[0]+1;  
}  
  
int main() {  
    ll t;  
    cin >> t;  
    REP(i, t) {  
        ll n;  
        cin >> n;  
        ll pair = (n - prime_count(n) + prime_count(n/2) - 1) / 2;  
        cout << n-pair << "\n";  
    }  
  
    return 0;  
}