t8m8-mem8

競プロとか、学んだことを書いていきます。

SRM 672 Div1 Easy: Procrastination

問題

Procrastination
社員が無限にいる会社がある。
社員其々に1つずつタスクが割り当てられており、始めは社員番号x番の社員にタスク番号x番が割り当てられている。社員番号は1から無限に続く。
h時間経過すると、社員番号がhより大きいhの倍数の社員は、社員番号が1つ大きい隣の社員とタスクを交換する(h=1のときは交換は行われないとする)。
hとnが与えられるので、h時間経過したときにn番のタスクが何番の社員が割り当てられているかを答えよ。

制約

 2 {\leq} n {\leq} 10^{10}

解法

2つの連続する素数の交換が行われないことを利用して探索範囲を絞り込むと良いらしい。
nより小さい素数とn以上の素数の間にある数が解候補なので、それらの数の因数を列挙していく。
因数を小さい順に見て、実際にシミュレーションすると最終的な解が得られる。

素数の間隔について調べてみたらこんな記事が出てきた。

tsujimotter.hatenablog.com

どうやら2つの連続する素数の間隔が600以下であることは証明されているらしい。
そもそも素数の間隔に上界があることを知らなかった。
この問題は区間を素数間にしないで適当な区間であたりをつけても通るっぽい。

public long findFinalAssignee(long n) {

    long lb = n-1, ub = n;

    while (!isPrime(lb)) lb--;
    while (!isPrime(ub)) ub++;

    TreeSet<Long> set = new TreeSet<Long>();

    for (long i=lb+1; i<=ub; i++) {
        for (long j=2; j*j<=i; j++) {
            if (i%j == 0) {
                set.add(j);
                set.add(i/j);
            }
        }
    }

    for (long h : set) {
        if (n%h == 0) {
            n++;
        } else if (n%h == 1) {
            n--;
        }
    }

    return n;
}

boolean isPrime(long n) {
    for (long i=2; i*i<=n; i++) {
        if (n%i == 0) return false;
    }
    return true;
}