はまやんはまやんはまやん

hamayanhamayan's blog

Collatz [yukicoder 887]

https://yukicoder.me/problems/no/887

解説

https://yukicoder.me/submissions/382000

制約を見てみると、シミュレートできそうな雰囲気がある。
400回までが上限なので、ぶん回す。

int n0;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> n0;

    int i1 = -1, nmax = n0;
    int n = n0;
    rep(i, 0, 400)
    {
        if (n == 1 and i1 < 0) {
            i1 = i;
            break;
        }

        chmax(nmax, n);

        if (n % 2 == 0)
            n = n / 2;
        else
            n = 3 * n + 1;
    }
    cout << i1 << endl;
    cout << nmax << endl;
}

約数の総和 [yukicoder 888]

https://yukicoder.me/problems/no/888

前提知識

解説

https://yukicoder.me/submissions/381998

約数列挙は O(sqrt(N))で行うことができる。
これをしていれば答えることができる問題。
やり方はここの約数列挙 O(sqrt(N))に概略がある。
制約が1012の場合は、計算量が O(sqrt(N))であるアルゴリズムを疑おう。

ll N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    auto ed = enumdiv(N);
    ll ans = 0;
    fore(x, ed) ans += x;
    cout << ans << endl;
}

Collatz [yukicoder 887]

https://yukicoder.me/problems/no/887

解説

https://yukicoder.me/submissions/382000

制約を見てみると、シミュレートできそうな雰囲気がある。
400回までが上限なので、ぶん回す。

int n0;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> n0;

    int i1 = -1, nmax = n0;
    int n = n0;
    rep(i, 0, 400)
    {
        if (n == 1 and i1 < 0) {
            i1 = i;
            break;
        }

        chmax(nmax, n);

        if (n % 2 == 0)
            n = n / 2;
        else
            n = 3 * n + 1;
    }
    cout << i1 << endl;
    cout << nmax << endl;
}

移調の限られた旋法 [yukicoder 890]

https://yukicoder.me/problems/no/890

前提知識

解説

https://yukicoder.me/submissions/382005

回転対称性について考える。
まず、beetさんが質問していたので見てみる。

回転対称性を持つとはある整数i(0<i<n)が存在して、任意の整数jに対して、  
j(mod N)番目の点が選ばれているかとj+i(mod N)番目の点が選ばれているかが  
同じであることです  

なるほど。
つまり、回転したときに同じになる場合は最初以外のどこかであればいいことになる。

こういう回転して、同じになるというのは周期性を用いる問題が多い。
円で考えず、列として考えたときに、同じパターンが連続する、つまり、周期性を持てば、回転すれば同じパターンになる場合が存在する。
そして、最小周期で全探索して数え上げしていく問題はいくつも見たことがある。
例えば、N=8であれば、最小周期が1,2,4である場合を考えればいい。

今回は選べる点の数がK個となっているが、最小周期をminloopとすると、グループはN/minloop個できる。
よって、KがN/minloopで割り切れる必要がある。そうでないと周期を作れない。
あとは、各周期について、最小周期がminloopとなるような列を構成すればいい。
これは、C(minloop, K/(N / minloop))をすればいい。
繰り返されるパターンを作るものである。

だが、これだけでは不十分で、こうして作られたパターンは周期がminloopであることは保証されるが、
最小周期がminloopでない可能性がある。
minloopの約数の周期になっている場合がある。
よって、この場合を引こう。
これは、約数系包除原理というテクである。
minloopの小さい方から計算をしていき、cnt[x] := 最小周期がxである組み合わせ
これを使って、ダブっているパターンを引いていく。

int N, K;
mint cnt[1010101];
Comb<mint, 2010101> com;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    auto ed = enumdiv(N);
    fore(minloop, ed) if (minloop < N and K % (N / minloop) == 0)
    {
        cnt[minloop] = com.aCb(minloop, K / (N / minloop));
        fore(x, ed) if (x < minloop and minloop % x == 0) cnt[minloop] -= cnt[x];
    }

    mint ans = 0;
    fore(minloop, ed) ans += cnt[minloop];
    cout << ans << endl;
}

隣接3項間の漸化式 [yukicoder 891]

https://yukicoder.me/problems/no/891

前提知識

解説

https://yukicoder.me/submissions/382008

問題を見るとフィボナッチ数の定義に似ている。
ある項のフィボナッチ数を高速に求める方法として、行列累乗が知られている。
今回の問題もこれで解ける。

int a, b, n;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> a >> b >> n;

    Mat m(2, Vec(2, 0));
    m[0][0] = 0;
    m[0][1] = 1;
    m[1][0] = b;
    m[1][1] = a;

    m = fastpow(m, n);

    Vec v(2, 0);
    v[0] = 0;
    v[1] = 1;

    v = mulMatVec(m, v);
    cout << v[0] << endl;
}

約数の総和 [yukicoder 888]

https://yukicoder.me/problems/no/888

前提知識

解説

https://yukicoder.me/submissions/381998

約数列挙は O(sqrt(N))で行うことができる。
これをしていれば答えることができる問題。
やり方はここの約数列挙 O(sqrt(N))に概略がある。
制約が1012の場合は、計算量が O(sqrt(N))であるアルゴリズムを疑おう。

ll N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    auto ed = enumdiv(N);
    ll ans = 0;
    fore(x, ed) ans += x;
    cout << ans << endl;
}

素数! [yukicoder 889]

https://yukicoder.me/problems/no/889

解説

https://yukicoder.me/submissions/382002

いろいろな種類の数に対する判定をする問題。
こういうものは関数化してライブラリとして持っておこう。
完全数判定なんて、どこで使うかわからないが、いつか役立ったりする。
全部の判定問題は基本的には、 O(sqrt(N))の素数判定を改造したものになる。

int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    if (2 <= N and isprime(N)) cout << "Sosu!" << endl;
    else if (2 <= N and isSquare(N)) cout << "Heihosu!" << endl;
    else if (2 <= N and isCubic(N)) cout << "Ripposu!" << endl;
    else if (isPerfectNumber(N)) cout << "Kanzensu!" << endl;
    else cout << N << endl;
}