解题思路

把 $x$ 的数字重排得到 $y$，且 $y$ 不能有前导 0。等价于：在与 $x$ 同位数的完全平方数里，统计数字频次与 $x$ 完全一致的个数。做法：

1. 记位数 $L$，枚举所有平方 $s=r^2$ 落在 $[10^{L-1},\,10^L-1]$；
2. 用长度为 10 的数组统计数字频次（0~9），与 $x$ 的频次比较，相同则计入答案。 直接枚举平方避免前导 0 且天然去重。

复杂度分析

设 $L=\text{len}(x)$，根的个数约为 $O(10^{L/2})$。 每次比较是 O(10)，总体时间 $O(10^{L/2})$，空间 O(1)。

代码实现

Python

import sys, math

# 统计数字频次
def sig(n: int):
    c = [0]*10
    if n == 0: c[0] = 1
    while n > 0:
        c[n % 10] += 1
        n //= 10
    return c

# 计算答案
def solve_one(x: int) -> int:
    L = len(str(x))
    low, high = 10**(L-1), 10**L - 1
    r1, r2 = math.isqrt(low - 1) + 1, math.isqrt(high)
    sx, ans = sig(x), 0
    for r in range(r1, r2 + 1):
        if sig(r*r) == sx:
            ans += 1
    return ans

def main():
    it = list(map(int, sys.stdin.read().strip().split()))
    T, idx = it[0], 1
    out = []
    for _ in range(T):
        out.append(str(solve_one(it[idx]))); idx += 1
    print("\n".join(out))

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {

    // 数字频次
    static int[] sig(long n) {
        int[] c = new int[10];
        if (n == 0) { c[0] = 1; return c; }
        while (n > 0) { c[(int)(n % 10)]++; n /= 10; }
        return c;
    }

    // 比较频次是否相同
    static boolean same(int[] a, int[] b) {
        for (int i = 0; i < 10; i++) if (a[i] != b[i]) return false;
        return true;
    }

    // 单组求解
    static int solveOne(long x) {
        int L = Long.toString(x).length();
        long low = 1; for (int i = 1; i < L; i++) low *= 10; // 10^(L-1)
        long high = low * 10 - 1;
        // 用 double 求根，再微调，代码更短
        long r1 = (long)Math.ceil(Math.sqrt((double)(low)));
        long r2 = (long)Math.floor(Math.sqrt((double)(high)));
        while (r1*r1 < low) r1++;
        while ((r1-1)>=0 && (r1-1)*(r1-1) >= low) r1--;
        while (r2*r2 > high) r2--;
        while ((r2+1)*(r2+1) <= high) r2++;

        int[] sx = sig(x);
        int ans = 0;
        for (long r = r1; r <= r2; r++) {
            if (same(sig(r*r), sx)) ans++;
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int T = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < T; i++) {
            long x = sc.nextLong();
            sb.append(solveOne(x)).append('\n');
        }
        System.out.print(sb.toString());
        sc.close();
    }
}

C++

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

// 数字频次
array<int,10> sig(long long n){
    array<int,10> c{}; c.fill(0);
    if(n==0){ c[0]=1; return c; }
    while(n){ c[n%10]++; n/=10; }
    return c;
}

int solveOne(long long x){
    int L = (int)to_string(x).size();
    long long low = 1;
    for(int i=1;i<L;i++) low*=10;           // 10^(L-1)
    long long high = low*10 - 1;

    // 简洁求根并微调
    long long r1 = (long long)ceil(sqrt((long double)low));
    long long r2 = (long long)floor(sqrt((long double)high));
    while(r1*r1 < low) r1++;
    while(r2*r2 > high) r2--;

    auto sx = sig(x);
    int ans = 0;
    for(long long r=r1; r<=r2; ++r)
        if(sig(r*r)==sx) ++ans;
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; 
    if(!(cin>>T)) return 0;
    while(T--){
        long long x; cin>>x;
        cout<<solveOne(x)<<"\n";
    }
    return 0;
}

题目内容

Bingbong 特别喜欢完全平方数。

现在给定一个整数 $x$，你可以任意打乱数位，得到新的数字 $y$ ，要求打乱后不能存在前导 $0$ 。

Bingbong 希望 $y$ 是一个完全平方数，请你帮他计算一下共有多少种不同的 $y$ 。

请注意：两种不同的操作方案，若结果相同则是属于同一种。

输入描述

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

一个整数 $x(1 ≦ x ≦ 10^9)$ ，为给定的数字。

输出描述

输出包含 $T$ 行，每行一个整数，表示不同的结果个数。

样例1

输入

2
414
1

输出

2
1