题目链接：Codeforces 70C

在海象国，一张车票由 $2$ 个数字组成 $(a,b)$，表示第 $a$ 系列车票的第 $b$ 张。定义一张车票是幸运的当且仅当 $a\times b=\text{rev}(a)\times\text{rev}(b)$，其中 $\text{rev}(x)$ 函数是将 $x$ 在十进制下翻转的结果（去掉前导零）。

交通管理委员会想新发布 $x$ 个系列的车票，每个系列包含 $y$ 张车票，要求这里面至少有 $w$ 张幸运的车票，并且车票总数 $x\times y$ 要尽量少。系列号由 $1$ 到 $x$ 标号，车票号由 $1$ 到 $y$ 标号。委员会要求不能发布超过 $\max_x$ 个系列，每个系列不能超过 $\max_y$ 张车票。无解输出 $-1$。

数据范围：$1\le \max_x,\max_y\le 10^5$，$1\le w\le 10^7$。

Solution

我们考虑把 $(i,\text{rev}(i))$ 存进一个 $\text{map}​$，表示这样的组合有多少个。

首先判断无解情况，我们把 $1$ 到 $\max_x$ 都加入，然后求出满足条件的最小 $y$。如果在 $1$ 到 $\max_y$ 范围内没有满足条件的 $y$ 则无解。

此时我们贪心确定了 $x(\max_x)$ 和 $y$ 的值。尝试缩小 $x$ 的值，减去贡献；如果此时幸运车票数量少于 $w$ 那么增大 $y​$ 的值直到满足条件位置（显然解有单调性），在此过程中不断更新答案即可。

时间复杂度：$\mathcal O(\max_x\log \max_x)$。

Code

#include <cstdio>
#include <algorithm>
#include <map>

const int N = 1e5 + 5;

int mx, my, w, r[N];
std::map<std::pair<int, int>, int> mpx, mpy;

int rev(int x) {
    int s[10], len=0;
    for (; x; s[++len] = x % 10, x /= 10);
    int ans = 0;
    for (int i = 1; i <= len; i++) {
        ans = 10 * ans + s[i];
    }
    return ans;
}
std::pair<int, int> calc(int x, bool flg) {
    int y = r[x], g = std::__gcd(x, y);
    if (flg) std::swap(x, y);
    return std::make_pair(x / g, y / g);
}
int init(int &ans) {
    for (int i = 1; i <= my; i++) {
        std::pair<int, int> t = calc(i, 1);
        ans += mpx[t], mpy[t]++;
        if (ans >= w) return i;
    }
    return 0;
}
int main() {
    scanf("%d%d%d", &mx, &my, &w);
    for (int i = 1; i <= 100000; i++) {
        r[i] = rev(i);
    }
    for (int i = 1; i <= mx; i++) {
        mpx[calc(i, 0)]++;
    }
    int sum = 0, y = init(sum), x = mx;
    if (sum < w) {
        puts("-1");
        return 0;
    }
    int ans = x * y, ansx = x, ansy = y;
    while (x) {
        mpx[calc(x, 0)]--;
        sum -= mpy[calc(x, 0)];
        x--;
        while (y < my && sum < w) {
            y++;
            mpy[calc(y, 1)]++;
            sum += mpx[calc(y, 1)];
        }
        if (x <= mx && y <= my && sum >= w && x * y < ans) {
            ans = x * y, ansx = x, ansy = y;
        }
    }
    printf("%d %d\n", ansx, ansy);
    return 0;
}