SRM 672 div1 easy:Procrastination

問題

TopCoder Statistics - Problem Statement

解法

n 以上で最小の素数を p1, n 未満で最大の素数を p2 とすると, 実は n 番目の task を持っている人は p2 より大きく p1 以下の番号の人に絞られます。これは, 任意の素数 p に対して p と p+1 の swap が起きないことから明らかです。

ということで, p1〜p2-1 の約数を全列挙してシミュレーションしましょう。素数は 1/log n の確率で現れるので, p2-p1 はまぁ 500 くらいで抑えられ, それらの約数がすべて O(sqrt(n)) だけあったとしてもシミュレーションは十分間に合います。

const ll INF = 1ll<<55;

bool prime(ll n) {
    for (ll i = 2; i*i <= n; i++) if (n%i == 0) return false;
    return true;
}

class Procrastination {
public:
    long long findFinalAssignee(long long n) {
        // n 以上の素数を探す
        ll up = n;
        while (!prime(up)) up++;
        // n 未満最大の素数を探す
        ll lp = n-1;
        while (!prime(lp)) lp--;
        // lp+1 ~ up の約数を列挙
        vector<ll> divs;
        for (ll i = lp+1; i <= up; i++) {
            for (ll j = 2; j*j <= i; j++) if (i%j == 0) {
                divs.push_back(j);
                divs.push_back(i/j);
            }
        }
        sort(divs.begin(), divs.end());
        divs.erase(unique(divs.begin(), divs.end()), divs.end());
        for (ll el : divs) {
            if ((n-1)%el == 0) n--;
            else if (n%el == 0) n++;
        }
        return n;
    }