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

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

输入格式
一个正整数。

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

数据范围
1≤N<10^6
输入样例1：
100
输出样例1：
11
输入样例2：
105
输出样例2：
6

代码：
优化前 3000ms

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15;
int n;
int num[N],cnt,res;
bool v[N];
//计算num数组中一段的数是多少
int substr(int s,int e)
{int res = 0;for(int i=s; i<=e; ++i){res = res * 10 + num[i];}return res;
}
bool check(int a,int b,int c)
{if(b%c!=0)return false;if(n == a + b/c){return true;}else return false;
}void dfs(int u)
{if(u == 9){// for (int i = 1; i <= 9; i ++ ){//     cout<<num[i]<<' ';// }cout<<endl;for(int i=0; i<7; ++i){for(int j=i+1; j<8; ++j){int a = substr(0,i);int b = substr(i+1,j);int c = substr(j+1,8);if(check(a,b,c)){res++;}}}/*for(int i = 0; i < 7; i++)for(int j = i + 1; j < 8; j++){int a = calc(0, i);int b = calc(i + 1, j);int c = calc(j + 1, 8);//注意判断条件，因为C++中除法是整除，所以要转化为加减乘来计算if(a * c + b == c * n) res++;}*/return ;}for(int i=1; i<=9; ++i){if(!v[i]){v[i] = true;num[u] = i;dfs(u+1);v[i] = false;}}
}
int main()
{cin>>n;dfs(0);cout<<res<<endl;return 0;
}

优化后 1000ms

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15;
int n;
int num[N],cnt,res;
bool v[N],mv[N];
//将题目拆解为 n = a + b/cbool check(int a,long long b,int c)
{if(!a||!b||!c) return false;//复制一份，防止这里的判断影响递归的结果memcpy(mv,v,sizeof(v));while(b){int t = b%10;b/=10;if (!t || mv[t]) return false;mv[t] = true;}for(int i=1; i<=9; ++i){if(!mv[i])  return false;}return true;
}
//枚举c
void dfs_c(int u,int a,int c)
{if(u == 10){return ;}long long b = (long long)c*n - (long long)a*c;if(check(a,b,c)){res++;}for (int i = 1; i <= 9; i ++ ){if(!v[i]){v[i] = true;dfs_c(u+1, a, c*10+i);v[i] = false;}}
}
//枚举a
void dfs_a(int u,int a)
{if(a>=n) return ;if(u == 10){return ;}if(a) dfs_c(u,a,0);for (int i = 1; i <= 9; i ++ ){if(!v[i]){v[i] = true;dfs_a(u+1,a*10+i);v[i] = false;}}
}
int main()
{cin>>n;dfs_a(0,0);cout<<res<<endl;return 0;
}