带分数

题目描述

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

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

输入格式

一个正整数。

输出格式

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

数据范围

1≤N<106

输入样例1：

100

输出样例1：

11

输入样例2：

105

输出样例2：

6

C ++代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 10;//N最大为1e6, 即N最多为7位

int ways[N];//存储排列结果
int used[N];//判断当前数字是否被用过
int x, res;

//将l~r之间的序列转化为数字
int cvt(int l, int r){
    int ans = 0;
    for(int i = l; i <= r; i ++){
        ans = ans * 10 + ways[i];
    }
    return ans;
}

void dfs(int u){
    if(u > 9){
        for(int i = 1; i <= 6; i ++)//a最多不超过n的位数且不大于1e6,即a最多为6位
            for(int j = i + 1; j <=8; j ++){
                int a = cvt(1, i);
                int b = cvt(i + 1, j);
                int c = cvt(j + 1, 9);
                if(x * c == a * c + b) res ++;
            }
        return ;
    }

    for(int i = 1; i <= 9; i ++){
        if(!used[i]){
            ways[u] = i;
            used[i] = true;
            dfs(u + 1);

            //恢复现场
            ways[u] = 0;
            used[i] = false;
        }
    }
}

int main(){
    scanf("%d", &x);

    dfs(1);

    printf("%d", res);

    return 0;
}