链接：https://atcoder.jp/contests/abc400

A – ABC400 Party

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int n;
    cin >> n;

    if (400 % n)
        cout << -1 << endl;
    else
        cout << 400 / n << endl;
}

B – Sum of Geometric Series

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    ll n, m;
    cin >> n >> m;

    __int128_t ans = 0;
    for (int i = 0; i <= m; ++i)
    {
        __int128_t t = pow(n, i);
        if (ans + t > 1e9)
        {
            cout << "inf" << endl;
            return;
        }
        ans += t;
    }

    cout << (ll)ans << endl;
}

C – 2^a b^2

算法：

    数论。

思路：

    当 \(a > 2\) 时，\(2 ^ {a – 2} * (2b) ^ 2\)，在此之前已经计算过了，所以只用计算 \(a = 1\)，\(a = 2\) 的情况。

    在确定 \(a\) 之后，\(b = sqrt(n / a)\)，直接计算即可。

关键代码：

void miyan()
{
    ll n;
    cin >> n;

    cout << ll(sqrtl(n / 2)) + ll(sqrtl(n / 4)) << endl;
}

D – Takahashi the Wall Breaker

算法：

    \(01bfs\)。

思路：

    建图：

    一个点到 '.' 的边权为 \(0\)，到 '#' 的边权为 \(1\)。

    只有两种边权，考虑双端队列。

关键代码：

void miyan()
{
    int n, m, x1, x2, y1, y2;
    cin >> n >> m;
    vector<string> g(n);
    for (int i = 0; i < n; ++i)
        cin >> g[i];
    cin >> x1 >> y1 >> x2 >> y2;
    --x1, --x2, --y1, --y2;

    vector dist(n, vector<int>(m, INT_MAX));
    auto bfs = [&]() -> void
    {
        deque<pii> q;
        dist[x1][y1] = 0;
        q.push_front({x1, y1});

        while (q.size())
        {
            auto [x, y] = q.front();
            q.pop_front();

            for (int i = 0; i < 4; ++i)
            {
                int a = x + dx[i], b = y + dy[i];
                if (a < 0 || a >= n || b < 0 || b >= m)
                    continue;

                if (g[x][y] == '.')
                {
                    if (dist[a][b] > dist[x][y])
                    {
                        dist[a][b] = dist[x][y];
                        q.push_front({a, b});
                    }
                }
                else
                {
                    if (dist[a][b] > dist[x][y] + 1)
                    {
                        dist[a][b] = dist[x][y] + 1;
                        q.push_back({a, b});
                    }

                    a += dx[i], b += dy[i];
                    if (a < 0 || a >= n || b < 0 || b >= m)
                        continue;
                    if (dist[a][b] > dist[x][y] + 1)
                    {
                        dist[a][b] = dist[x][y] + 1;
                        q.push_back({a, b});
                    }
                }
            }
        }
    };

    bfs();

    cout << dist[x2][y2] << endl;
}

E – Ringo’s Favorite Numbers 3

算法：

    数论。

思路：

    由算术基本定理：

\(n = p_1^{a_1} \cdot p_2^{a_2} \cdot p_3^{a_3} \cdots p_k^{a_k}\)

    题目给出 \(n\) 满足以下条件：

• 只有两个不同的质因子；
• 每个质因子都出现偶数次。

    那么 \(n = p_1^{a_1} \cdot p_2^{a_2}\)，其中 \(a_1\) 和 \(a_2\) 都是偶数。

    那么就有 \(m = p_1 ^ {a_1 / 2} * p_2 ^ {a_2 / 2}\)

    那么本题就转换为：

• \(n\) 只有两不同的质因子；
• \(n\) 是一个完全平方数。

    由于 \(m ^ 2 = n\)，\(n = 1e12\)，那么 \(m = 1e6\)，直接枚举每一个 \(m\)，并对其质因数分解，判断其质因子个数即可。

关键代码：

vector<int> prime, minp;
void get_prime(int n)
{
    minp.resize(n + 1);
    for (int i = 2; i <= n; i++)
    {
        if (!minp[i])
        {
            minp[i] = i;
            prime.push_back(i);
        }
        for (auto j : prime)
        {
            if (j > minp[i] || j > n / i)
                break;
            minp[i * j] = j;
        }
    }
}

vector<ll> ans;
void init()
{
    get_prime(N);

    for (ll i = 6; i < N; ++i)
    {
        ll x = i;
        set<int> s;
        while (x > 1)
        {
            int now = minp[x];
            s.insert(minp[x]);
            while (x % now == 0)
            {
                x /= now;
            }
        }

        if (s.size() == 2)
            ans.push_back(i * i);
    }
}

void miyan()
{
    ll n;
    cin >> n;

    auto it = ranges::upper_bound(ans, n);
    --it;
    cout << *it << endl;
}

F – Happy Birthday! 3

    还没补。