Gym102788，B - Rectangles题解

标签：std int 题解 back 4n 2n Rectangles primes Gym102788

水水水~
题目链接戳我

分析

首先根据题目条件可得式子=>\((x - 2)(y - 2) = n(2x + 2y - 4)\)
化简式子可得

\[\begin{align} (x - 2)(y - 2) = &n(2x + 2y - 4)\\ xy - 2x - 2y + 4 = &2nx + 2ny - 4n \\ x(y - 2n - 2) = &2ny - 4n - 4 + 2y \\ x = &\frac{2ny - 4n - 4 + 2y - 4n^2 + 4n^2 - 4n + 4n}{y - (2n + 2)} \\ x = &\frac{(2n + 2)(y - 2n - 2) + 4n^2 + 4n}{y - (2n + 2)} \\ x = &2n + 2 + \frac{4n^2 + 4n}{y - (2n + 2)} \end{align} \]

可以发现对于\(\frac{4n^2 + 4n}{y - (2n + 2)}\)这个式子想让其条件\((y - 2n - 2)|(4n^2 + 4n)\)成立，只能是\(y-(2n + 2)\)为\(4n^2 + 4n\)的因子，因此我们只需求出\(4n^2 + 4n\)的所有因子即可得到所有的(x, y)对。

具体实现

#include <bits/stdc++.h>

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
namespace Factorizer {
    std::vector<int> primes;
    std::vector<int> least;
    void sieve(int n) {
        std::vector<int> nums;
        least.assign(n + 1, 0);
        for (int i = 2; i <= n; ++i) {
            if (least[i] == 0) {
                least[i] = i;
                nums.push_back(i);
            }
            int now = 0;
            while (now < (int)nums.size()
                && nums[now] <= least[i] && i * nums[now] <= n) {
                least[i * nums[now]] = nums[now];
                now += 1;
            }
        }
        primes = nums;
    }
    constexpr bool miller_rabin(long long n) {
        if (n <= 1 || (n != 2 && n % 2 == 0)) return false;
        for (auto a : {3, 5, 7, 11, 13, 17, 19, 23, 29}) {
            if (n % a == 0) return n == a;
        }
        if (n < 31 * 31) return true;
        long long d = n - 1;
        while (d % 2 == 0) d /= 2;
        constexpr long long bases[] = {
            2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37
        };
        for (long long a : bases) {
            if (n == a) return true;
            long long t = d;
            long long y = 1 % n;
            for (long long _t = t; _t != 0; _t >>= 1) {
                if (_t & 1) y = (__int128) y * a % n;
                a = (__int128) a * a % n;
            }
            while (t != n - 1 && y != 1 && y != n - 1) {
                y = (__int128) y * y % n;
                t <<= 1;
            }
            if (y != n - 1 && t % 2 == 0) return false;
        }
        return true;
    }
    long long pollard_rho(long long n) {
        if (n == 1 || miller_rabin(n)) return n;
        long long now = 0;
        do {
            long long t = std::gcd(++now, n), r = t;
            if (t != 1 && t != n) return t;
            long long g = 1;
            do {
                t = ((__int128) t * t % n + now) % n;
                r = ((__int128) r * r % n + now) % n;
                r = ((__int128) r * r % n + now) % n;
            } while ((g = std::gcd(abs(t - r), n)) == 1);
            if (g != n) return g;
        } while (now < n / now);
        return 0;
    }
    std::vector<long long> factor(long long n) {
        if (n == 1) return {};
        std::vector<long long> g, d;
        d.push_back(n);
        while (!d.empty()) {
            auto v = d.back();
            d.pop_back();
            auto rho = pollard_rho(v);
            if (rho == v) {
                g.push_back(rho);
            } else {
                d.push_back(rho);
                d.push_back(v / rho);
            }
        }
        std::sort(g.begin(), g.end());
        return g;
    }
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    #define int long long
    int n;
    std::cin >> n;  
    std::vector<int> primes = Factorizer::factor(4LL * n * n + 4LL * n);
    std::vector<std::pair<int, int>> fact;
    for (int i = 0; i < (int)size(primes); ++i) {
        int j = i + 1;
        while (j < (int)size(primes) && primes[i] == primes[j]) {
            j += 1;
        }
        fact.emplace_back(primes[i], j - i);
        i = j - 1;
    }
    std::vector<std::pair<int, int>> ans;
    auto power = [&](int a, int b) {
        int c = 1;
        for (; b; a *= a, b >>= 1)
            if (b & 1) c *= a;
        return c;
    };
    int num = 0;
    auto dfs = [&](auto &&self, int u, int f) {
        int y = f + (2 * n + 2), x = 2 * (n + 1) + 4 * n * (n + 1) / (y - 2 * n - 2);
        if (x > y) {
            std::swap(x, y);
        }
        ans.emplace_back(x, y);
        if (u == size(fact)) return ;
        auto [p, cnt] = fact[u];
        // debug(p, cnt);
        for (int i = 0; i <= cnt; ++i) {
            debug(u + 1, f * power(p, i));
            self(self, u + 1, f * power(p, i));
        }
    };
    dfs(dfs, 0, 1);
    std::sort(ans.begin(), ans.end());
    ans.erase(std::unique(ans.begin(), ans.end()), ans.end());
    std::cout << size(ans) << '\n';
    for (auto [x, y] : ans) {
        std::cout << x << ' ' << y << '\n';
    }
}

标签：std,int,题解,back,4n,2n,Rectangles,primes,Gym102788
From： https://www.cnblogs.com/sleeeeeping/p/18346919