欢迎关注

题目描述

100 可以表示为带分数的形式：100=3+69258/714
还可以表示为：100=82+3546/197
注意特征：带分数中，数字 1∼9 分别出现且只出现一次（不包含 0）。

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

输入格式

输入样例

100

输出样例

6

分析

大佬都自己写递归，唉可是我这个蒟蒻只会用函数。题目要求1-9中每个数都用一次，这个时时候我们很容易想到全排列，其实algorithm头文件里面有一个next_permutation函数可以直接拿过来用哈哈哈，这个函数会生成当前序列的下一个全排列序列，具体使用方法见代码。

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, ans;
int a[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
// 求出这个数
int getNum(int l, int r)
{
    int res = 0;
    for (int i = l; i <= r; i++)
    {
        res = res * 10 + a[i];
    }
    return res;
}
//  判断a == a + b / c
bool check(int a, int b, int c)
{
    if (b % c != 0)
    {
        return false;
    }
    if (a + b / c != n)
    {
        return false;
    }
    return true;
}
int main()
{
    cin >> n;
    do{
        for (int i = 0; i < 6; i++)// 数据范围是n < 1000000
        {
            for (int j = i + 1; j < 8; j++)// c必须大于0，所以要给c留出一位
            {
                int a = getNum(0, i);
                int b = getNum(i + 1, j);
                int c = getNum(j + 1, 8);
                if (check(a, b, c))
                {
                    ans++;
                }
            }
        }
    }while(next_permutation(a, a + 9));
    printf("%d\n", ans);
    return 0;
}