けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

再帰的構造を見出して解く 2 つの難問

再帰的構造に着目する

Tenka1 F ModularPowerEquation!! に挑んだときに「再帰的に解ける」ことに気づかずに苦渋を飲んだにもかかわらず、CODE FESTIVAL 2017 QualB F Largest Smallest Cyclic Shift で同じように「再帰的に解ける」ことを見逃してしまったので、もう二度と見逃すまいという思いを込めて記録つけるのん。

Tenka1 F ModularPowerEquation!!

以下の Q 個のクエリに答えてください。

整数 A_i, M_i が与えられます。 A_i^{K_i} ≡ K_i (mod M_i) なる 2×1018 以下の正整数 K_i が存在するか判定し、存在するならひとつ求めてください。

  • 1 \le Q \le 100
  • 0 \le A_{i} \le 10^{9}
  • 1 \le M_{i} \le 10^{9}

まず A と M が互いに素なら、Euler の定理より、

A^{\phi(M)} ≡ 1 (mod. M)

が成立します。A と M が互いに素でなくても、A の指数が十分大きくなれば、

A^{L + \phi(M)} ≡ A^{L} (mod. M)

といったように、周期 \phi(M) で循環することを示すことができます。具体的には A と M が共通の素因子 p をもつとしても、 L \ge {\rm ord}_p M \ge 30 ならば、大丈夫なことがわかります。

よって、A の指数について \phi(M) の周期があるから、今度は

A^{x} ≡ x (mod. \phi(M) )

となるような x が見つかれば、

A^{A^{x}}≡A^{x} (mod. M)

となることが言えます。よく見ると、A^{x} ≡ x (mod. \phi(M) ) の式は、mod の値が小さくなった問題を再帰的に解く構造になっています。

なお、 A^{x} を毎回出力していたのでは大きすぎるので、{\rm LCM}(\phi(M), M) で割ったあまり (のうち 30 以上のもの) を出力すればよいです。

\phi ( \phi(M) ) < M/2 が言えるので、計算時間は縮小法から O(\sqrt{M}) になります。

#include <iostream>
#include <vector>
using namespace std;

inline long long mod(long long a, long long m) {
    return (a % m + m) % m;
}

inline long long mul(long long a, long long b, long long m) {
    a = mod(a, m); b = mod(b, m);
    if (b == 0) return 0;
    long long res = mul(mod(a + a, m), b>>1, m);
    if (b & 1) res = mod(res + a, m);
    return res;
}

long long pow(long long a, long long n, long long m) {
    if (n == 0) return 1 % m;
    long long t = pow(a, n/2, m);
    t = mul(t, t, m);
    if (n & 1) t = mul(t, a, m);
    return t;
}

vector<pair<long long, long long> > prime_factor(long long n) {
    vector<pair<long long, long long> > res;
    for (long long i = 2; i*i <= n; ++i) {
        if (n % i == 0) {
            int exp = 0;
            while (n % i == 0) {
                ++exp;
                n /= i;
            }
            res.push_back(make_pair(i, exp));
        }
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}
long long GCD(long long a, long long b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}
long long LCM(long long a, long long b) {
    long long g = GCD(a, b);
    return a / g * b;
}

const long long L = 50;
long long solve(long long A, long long M) {
    if (A == 0) return M;
    if (A == 1) return 1;
    if (M == 1) return L;
    long long phiM = M;
    vector<pair<long long, long long> > divM = prime_factor(M);
    for (int i = 0; i < divM.size(); ++i) {
        long long p = divM[i].first;
        phiM *= p - 1;
        phiM /= p;
    }
    long long y = solve(A, phiM);
    long long lcm = LCM(phiM, M);
    long long res = pow(A, y, lcm);
    while (res < L) res += lcm;
    return res;
}
int main() {
    int Q;
    while (cin >> Q) {
        for (int i = 0; i < Q; ++i) {
            long long a, m; cin >> a >> m;
            long long res = solve(a, m);
            cout << res << endl;
        }
    }
}

CODE FESTIVAL 2017 QualB F Largest Smallest Cyclic Shift

文字列 S に対し、f(S) を S の巡回シフトのうち辞書順最小のものとする。
'a' が X 個、'b' が Y 個、'c' が Z 個で構成される文字列 T のうち、 f(T) が辞書順最大となるものを求め、その f(T) を出力せよ。

・1 <= X + Y + Z <= 50
・X, Y, Z >= 0

これの解法については、sigma さんの素晴らしい解説があるので、そちらに譲ります。

aaac, aab, aac のようなものを並び替えればいい (場合分けの 1 つめのとき) といったことには思いが至ったにもかかわらず、再帰的に解けばよいことに気付けなかったので要反省です。

#include <iostream>
#include <string>
using namespace std;
string solve(string a, string b, string c, int x, int y, int z) {
       if (y + z == 0) {
              string res = "";
              for (int i = 0; i < x; ++i) res += a;
              return res;
       }
       if (x == 0) return solve(b, c, "", y, z, 0);
       int p = x / (y + z);
       int r = x % (y + z);
       string A = "";
       for (int i = 0; i < p; ++i) A += a;
       if (z >= r) return solve(A + a + c, A + b, A + c, r, y, z - r);
       else return solve(A + a + b, A + a + c, A + b, r - z, z, y + z - r);
}
int main() {
       int x, y, z;
       while (cin >> x >> y >> z) {
              cout << solve("a", "b", "c", x, y, z) << endl;
       }
}