WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM672 Div1 Easy "Procrastination"

解法

こちらを完コピしました。。orz

t8m8.hateblo.jp


事後

ソースが簡潔でいいですなぁ

ソースコード

class Procrastination {
    public:
    long long findFinalAssignee(long long n) {

        // nより小さい最大の素数と
        // n以上の最小の素数を求める
        long long lp = n - 1;
        long long rp = n;
        while (!isPrime(lp)) lp--;
        while (!isPrime(rp)) rp++;

        // lp < x <= rp のすべての約数を求める
        set<long long> s;
        for (long long x = lp + 1; x <= rp; x++) {
            for (long long d = 2; d * d <= x; d++) {
                if (x % d == 0) {
                    s.insert(d);
                    s.insert(x / d);
                }
            }
        }

        // シミュレートしていく
        for (auto f : s) {
            if (n % f == 0) {
                n++;
            } else if (n % f == 1) {
                n--;
            }
        }

        return n;
    }

    // 素数か?
    bool isPrime(long long n) {
        for (long long d = 2; d * d <= n; d++) {
            if (n % d == 0) return false;
        }
        return true;
    }

};