Project Euler 411

题目

Uphill paths

Let \(n\) be a positive integer. Suppose there are stations at the coordinates \((x, y) = (2^i \bmod n, 3^i \bmod n)\) for \(0 \le i \le 2n\). We will consider stations with the same coordinates as the same station.

We wish to form a path from \((0, 0)\) to \((n, n)\) such that the \(x\) and \(y\) coordinates never decrease.

Let \(S(n)\) be the maximum number of stations such a path can pass through.

For example, if \(n = 22\), there are \(11\) distinct stations, and a valid path can pass through at most \(5\) stations. Therefore, \(S(22) = 5\).

The case is illustrated below, with an example of an optimal path:

It can also be verified that \(S(123) = 14\) and \(S(10000) = 48\).

Find \(\sum S(k^5)\) for \(1 \le k \le 30\).

解决方案

令\(P_n=\{(2^i\bmod n,3^i\bmod n)\mid 0\le i\le 2n\},\)把每个站点当作一个点 \((x,y)\)，可达关系就是坐标逐点不降：\((x_1,y_1)\preceq (x_2,y_2)\iff x_1\le x_2,y_1\le y_2.\)于是 \(S(n)\) 就是这个二维偏序中的最长链长度。

将所有站点按字典序排序（\(x\)是第一关键字升序，\(y\)是第二关键字升序排序），得到序列\((x_1,y_1),(x_2,y_2),\dots,(x_m,y_m).\)此时：若选出下标递增的若干点且其 \(y\) 非下降，那么 \(x\) 也必然非下降（因已按 \(x\) 排序），故对应一条合法路径；任意合法路径在该排序下都会保持下标递增，且 \(y\) 非下降。

因此\(S(n)\)就是即排序后 \(y\) 序列的最长非下降子序列长度。这一步也可写成经典 DP：\(\displaystyle f(y)=1+\max_{t\le y}f(t),\)其中 \(f(y)\)表示以纵坐标不超过\(y\)的位置结尾时，最多能经过多少个站点。因此每一步都需要查询区间 \([0,y]\) 的最大值并更新位置 \(y\)，可用树状数组维护前缀最大值实现。

不过，直接算到 \(2n\) 再排序和去重会很慢。真正需要的是第一次重复前的全部状态。

令\(n=2^a3^b m,\gcd(m,6)=1.\)记\(x_i=2^i\bmod n, y_i=3^i\bmod n.\)

考虑\(x_i\)的结构。在模 \(2^a\) 分量上，\(i\ge a\) 后恒为 \(0\)；在模 \(n/2^a\) 分量上，\(2\) 与模数互素，从一开始就纯周期，周期为\(\lambda_X=\lambda_{n/2^a}(2).\)所以 \(x_i\) 的预周期长度是 \(a\)，最终周期是 \(\lambda_X\)。

再考虑\(x_i\)的结构。同理：预周期长度 \(b\)；最终周期\(\lambda_Y=\lambda_{n/3^b}(3).\)

最终，点对 \((x_i,y_i)\) 的预周期长度是\(\mu=\max(a,b),\)因此最终周期是\(\lambda=\operatorname{lcm}(\lambda_X,\lambda_Y).\)

因此不同站点恰好是前\(M=\mu+\lambda\)项。只生成这 \(M\) 项即可（无需哈希去重）。

代码

#include <bits/stdc++.h>
#include "tools.h"
using namespace std;

typedef long long ll;

const int K = 30;
const int P = 5;
const int M = pow(K, P);
Factorizer fc = Factorizer(M);

ll multiplicative_order(ll a, ll m)
{
    if (m == 1)
        return 1;
    auto fm = fc.factor_small(m);
    ll phi = 1;
    for (auto &pe : fm)
    {
        ll p = pe.first;
        int e = pe.second;
        ll t = 1;
        for (int i = 0; i < e - 1; ++i)
            t *= p;
        phi *= (p - 1) * t;
    }
    auto fp = fc.factor_small(phi);
    ll ord = phi;
    for (auto &pe : fp)
    {
        ll p = pe.first;
        while (ord % p == 0 && qpow(a, ord / p, m) == 1)
            ord /= p;
    }
    return ord;
}

pair<ll, ll> preperiod_period(ll n)
{
    ll t = n;
    int a = 0, b = 0;
    while ((t & 1) == 0)
    {
        ++a;
        t >>= 1;
    }
    t = n;
    while (t % 3 == 0)
    {
        ++b;
        t /= 3;
    }
    ll mu = max(a, b);

    ll m2 = n, m3 = n;
    for (int i = 0; i < a; ++i)
        m2 /= 2;
    for (int i = 0; i < b; ++i)
        m3 /= 3;

    ll p2 = multiplicative_order(2, m2);
    ll p3 = multiplicative_order(3, m3);
    ll lam = p2 / gcd(p2, p3) * p3;
    return {mu, lam};
}

int S(int n)
{
    if (n == 1)
        return 1;

    auto [mu, lam] = preperiod_period(n);
    ll m = mu + lam;

    vector<ll> pts;
    pts.reserve(m);

    ll x = 1 % n, y = 1 % n;
    for (ll i = 0; i < m; ++i)
    {
        pts.push_back((ll(uint32_t(x)) << 32) | ll(uint32_t(y)));
        x = (x * 2) % n;
        y = (y * 3) % n;
    }

    sort(pts.begin(), pts.end());
    pts.erase(unique(pts.begin(), pts.end()), pts.end());

    vector<int> tails;
    for (ll v : pts)
    {
        int yy = int(uint32_t(v));
        auto it = upper_bound(tails.begin(), tails.end(), yy);
        if (it == tails.end())
            tails.push_back(yy);
        else
            *it = yy;
    }

    return (int)tails.size();
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long ans = 0;
    for (int k = 1; k <= K; ++k)
    {
        ll n = 1;
        for (int i = 0; i < P; ++i)
            n *= k;
        ans += S((int)n);
    }
    cout << ans << '\n';
    return 0;
}