解题思路

给定正整数 $m$，统计满足以下条件且不大于 $m$ 的整数个数：

• $n$ 的十进制表示是单调不降（上升数）；
• $n^2$ 的十进制表示也单调不降（超级上升数）。

核心做法：预处理 + 二分

1. 先写一个判定函数 is_nondec(x)：检查整数的十进制数字是否从左到右单调不降。

2. 用**深度优先搜索（回溯）**按位生成所有不超过 $10^{18}$ 的上升数：

   • 为了保证“上升数”，每次只能在当前最后一位 $d$ 的基础上继续添加 $\ge d$ 的数字。
   • 剪枝优化：观察可得，末位为 9 的数平方末两位一定是“81”（下降），因此全部不可能；在可行解中，数字 8 仅出现于特例 38（$38^2=1444$ 不下降）。因此 DFS 仅在数字 1..7 上扩展，并在结束后特判加入 38。这样搜索空间从约 690 万（完整 1..9）降到约 65 万，Python 也能轻松通过。

3. 对枚举出的每个上升数 $n$，判定 is_nondec(n*n)，若通过则加入数组 good。

4. 将 good 排序。对每个查询 $m$，用二分查找（上界 upper_bound）返回 good 中 $\le m$ 的元素个数。

说明：完整地在 1..9 上枚举也正确；上述剪枝仅为加速，正确性由“枚举 + 检验 $n^2$”保证。

复杂度分析

• 预处理：生成约 65 万个候选上升数，每个需要一次平方并做位序检查（$\le 37$ 位）。 时间复杂度约为 $O(S \cdot \log_{10}N)$（$S\approx 6.6\times10^5$，$N\le 10^{36}$），空间复杂度 $O(S)$ 存储结果（最终超级上升数仅 235 个）。
• 查询：每次二分 $O(\log K)$，其中 $K=235$ 极小，近似 $O(1)$。

代码实现

Python

# -*- coding: utf-8 -*-
# 题意：统计不大于 m 的“超级上升数”（n 与 n^2 的十进制表示均单调不降）

import sys
from bisect import bisect_right

LIMIT = 10 ** 18
good = []

def is_nondec(x: int) -> bool:
    """判断十进制是否单调不降（从左到右）"""
    s = str(x)
    for i in range(1, len(s)):
        if s[i] < s[i - 1]:
            return False
    return True

def dfs(last_digit: int, cur: int):
    """按位生成所有不超过 LIMIT 的上升数（仅用数字 1..7，加速）"""
    if cur > LIMIT:
        return
    if cur > 0:
        # cur 已是上升数，检查平方是否也是上升数
        if is_nondec(cur * cur):
            good.append(cur)
    # 只扩展到 7（8,9 大多不行，唯一可行 38 后面单独特判）
    for d in range(last_digit, 8):
        nxt = cur * 10 + d
        if nxt > LIMIT:
            break
        dfs(d, nxt)

def build():
    """预处理所有超级上升数"""
    dfs(1, 0)
    # 特判：38（实测唯一包含 8 的可行数）
    if LIMIT >= 38 and is_nondec(38 * 38):
        good.append(38)
    good.sort()

def solve():
    build()
    data = sys.stdin.read().strip().split()
    if not data:
        return
    t = int(data[0])
    idx = 1
    out_lines = []
    for _ in range(t):
        m = int(data[idx]); idx += 1
        # 统计 <= m 的数量：upper_bound
        ans = bisect_right(good, m)
        out_lines.append(str(ans))
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    solve()

Java

import java.io.*;
import java.math.BigInteger;
import java.util.*;

/**
 * ACM 风格：读取 T 组 m，输出每组答案
 * 预处理：DFS 生成所有上升数（仅用 1..7）+ 检查 n^2 是否单调不降
 * Java 使用 BigInteger 计算平方，避免 long 溢出
 */
public class Main {
    static final long LIMIT = 1_000_000_000_000_000_000L; // 1e18
    static ArrayList<Long> good = new ArrayList<>();

    // 判断字符串数字是否单调不降
    static boolean isNonDecStr(String s) {
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) < s.charAt(i - 1)) return false;
        }
        return true;
    }

    // 判断 n^2 的十进制是否单调不降（使用 BigInteger 安全平方）
    static boolean isNonDecSquare(long n) {
        BigInteger bn = BigInteger.valueOf(n);
        String sq = bn.multiply(bn).toString();
        return isNonDecStr(sq);
    }

    // DFS 生成上升数（仅 1..7），并筛到 good
    static void dfs(int lastDigit, long cur) {
        if (cur > LIMIT) return;
        if (cur > 0) {
            if (isNonDecSquare(cur)) good.add(cur);
        }
        for (int d = lastDigit; d <= 7; d++) {
            long nxt = cur * 10 + d;
            if (nxt > LIMIT) break;
            dfs(d, nxt);
        }
    }

    // 预处理所有超级上升数
    static void build() {
        dfs(1, 0L);
        // 特判 38
        if (LIMIT >= 38 && isNonDecSquare(38)) good.add(38L);
        Collections.sort(good);
    }

    // 上界二分：返回 <= x 的数量
    static int upperBound(ArrayList<Long> a, long x) {
        int l = 0, r = a.size();
        while (l < r) {
            int m = (l + r) >>> 1;
            if (a.get(m) <= x) l = m + 1; else r = m;
        }
        return l;
    }

    public static void main(String[] args) throws Exception {
        build();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder out = new StringBuilder();
        String s = br.readLine();
        if (s == null || s.trim().isEmpty()) {
            System.out.print("");
            return;
        }
        int T = Integer.parseInt(s.trim());
        for (int i = 0; i < T; i++) {
            long m = Long.parseLong(br.readLine().trim());
            int ans = upperBound(good, m);
            out.append(ans).append('\n');
        }
        System.out.print(out.toString());
    }
}

C++

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

/*
 * 思路：DFS 生成所有上升数（仅用 1..7，后续特判 38），
 *      用 __int128 计算 n^2 并判断其十进制是否单调不降。
 * 查询时对预处理数组做 upper_bound。
 */

const long long LIMIT_VAL = (long long)1e18;
vector<long long> good;

// 判断十进制是否单调不降（从左到右）
static bool is_nondec_u128(__int128 x) {
    // 将 x 的十进制从高到低比较：这里从低到高取位，保存到数组再检查
    if (x == 0) return true;
    vector<int> d;
    while (x > 0) { d.push_back((int)(x % 10)); x /= 10; }
    // 现在 d 是从低到高，逆序后从左到右检查
    for (int i = (int)d.size() - 1; i > 0; --i) {
        if (d[i] > d[i - 1]) return false; // 左 > 右 代表下降（因当前从高到低）
    }
    return true;
}

// 判断 n^2 的十进制是否单调不降
static bool square_nondec(long long n) {
    __int128 t = (__int128)n * (__int128)n;
    return is_nondec_u128(t);
}

// DFS：仅扩展数字 1..7（8、9 剪枝；38 单独特判）
static void dfs(int last_digit, long long cur) {
    if (cur > LIMIT_VAL) return;
    if (cur > 0) {
        if (square_nondec(cur)) good.push_back(cur);
    }
    for (int d = last_digit; d <= 7; ++d) {
        long long nxt = cur * 10 + d;
        if (nxt > LIMIT_VAL) break;
        dfs(d, nxt);
    }
}

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

    // 预处理
    dfs(1, 0);
    if (LIMIT_VAL >= 38 && square_nondec(38)) good.push_back(38);
    sort(good.begin(), good.end());

    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        long long m; cin >> m;
        // 统计 <= m 的数量：upper_bound
        cout << (upper_bound(good.begin(), good.end(), m) - good.begin()) << "\n";
    }
    return 0;
}

题目内容

定义一个正整数 $n$ 是上升数，当且仅当其十进制表示为单调不降的，如 $11223,9$，反之 $114514,1919810$ 则不是。

定义一个正整数 $n$ 是超级上升数，当且仅当 $n$ 为上升数，且 $n^2$ 也为上升数。

现在包包有一个正整数 $m$。你需要求出有多少个不大于 $m$ 的超级上升数。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤10^4)$ 代表数据组数，每组测试数据描述如下：

输入一行一个正整数 $m(1≤m≤10^{18})$ 。

输出描述

对于每组测试数据，输出一行一个整数，代表不大于 $m$ 的超级上升数的数量。

样例1

输入

3
5
8
13

输出

5
7
9

说明

不大于 $13$ 的超级上升数有：$1,2,3,4,5,6,7,12,13$ 。