题目描述

100可以表示为带分数的形式：100=3+69258/714

还可以表示为：100=82+3546/197

注意特征：带分数中，数字1∼9分别出现且只出现一次（不包含 0）。

类似这样的带分数，100有11种表示法。

输入格式
一个正整数。

输出格式
输出输入数字用数码 1∼9
不重复不遗漏地组成带分数表示的全部种数。

数据范围
1≤N<1e6

样例

输入样例1：
100
输出样例1：
11
输入样例2：
105
输出样例2：
6

算法1

深度优先搜索
剪枝

C++ 代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
bool used[10];
int a[10];
int b[10];
int c[10];
long long p10[11]; // 预计算 10 的幂
int a_length;
int b_length;
int c_length;
int cnt;

// 预计算 10^i (i=0...10)
void init_p10()
{
    p10[0] = 1;
    for (int i = 1; i <= 10; i++)
    {
        p10[i] = p10[i - 1] * 10;
    }
}

// c*n = c*a + b

// 枚举c的每一位，枚举d位
void dfs_c(int x, int d, int a_val, int c_val)
{
    if (x == d + 1)
    {
        c_length = d;
        b_length = 9 - a_length - c_length;
        if (b_length < 1)
            return;
        // 根据公式 b = c * (n - a)
        int b_val = c_val * (n - a_val);

        // 检查 b_val 的位数是否正好为 b_length
        // k 位的正整数都在区间 [10^(k-1), 10^k)
        if (b_val < p10[b_length - 1] || b_val >= p10[b_length])
            return;

        // 1. 构造一个 vector 存放全局 used 数组中未使用的数字（即 b 应该由这些数字构成）
        vector<int> remain;
        for (int d = 1; d <= 9; d++)
        {
            if (!used[d])
                remain.push_back(d);
        }

        // 2. 将 b_val 拆分为单个数字，存入 vector b_digits
        vector<int> b_digits;
        long long temp = b_val;
        while (temp)
        {
            int digit = temp % 10;
            temp /= 10;
            // 如果出现 0，则不合法，因为题目只允许使用 1～9
            if (digit == 0)
                return;
            b_digits.push_back(digit);
        }

        // 如果 b_digits 的数字个数不等于预期的 b_length，则说明不符
        if (b_digits.size() != (unsigned)b_length)
            return;

        // 3. 对两个 vector 排序，然后比较是否完全一致
        sort(remain.begin(), remain.end());
        sort(b_digits.begin(), b_digits.end());
        if (remain == b_digits)
            cnt++;

        return;
    }

    // 每一位枚举1-9
    for (int i = 1; i <= 9; i++)
    {
        if (!used[i])
        {
            used[i] = true;
            c[x] = i;
            dfs_c(x + 1, d, a_val, c_val * 10 + i);
            used[i] = false;
        }
    }
}

// 枚举a的每一位，枚举d位
void dfs_a(int x, int d, int a_val)
{
    if (x == d + 1)
    {
        a_length = d;
        if (a_length >= n)
            return;

        // 枚举完a后枚举c，枚举i位
        for (int i = 1; i <= 9 - d - 1; i++)
        {
            dfs_c(1, i, a_val, 0);
        }
        return;
    }

    // 每一位枚举1-9
    for (int i = 1; i <= 9; i++)
    {
        if (!used[i])
        {
            used[i] = true;
            a[x] = i;
            dfs_a(x + 1, d, a_val * 10 + i);
            used[i] = false;
        }
    }
}

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

    cin >> n;

    init_p10();

    for (int i = 1; i <= 7; i++)
    {
        dfs_a(1, i, 0);
    }
    cout << cnt;
    return 0;
}