问题描述 100 可以表示为带分数的形式：100 = 3 + 69258 / 714。
还可以表示为：100 = 82 + 3546 / 197。
注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。
类似这样的带分数，100 有 11 种表示法。
输入格式 从标准输入读入一个正整数N (N<1000*1000)
输出格式 程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法！
样例输入1 100 样例输出1 11 样例输入2 105 样例输出2 6
因为带分数是1-9有且仅出现一次，所以先用全排列，对每一种排列分成三段，分别对应第一个整数，分子和分母，再筛选一下就出来了。其实还有更优化的剪枝，不过这样已经够了
#include <iostream> #include <cstring> #include <string> #include <vector> #include <queue> #include <cstdio> #include <set> #include <cmath> #include <algorithm> #include <queue> #define INF 0x3f3f3f3f #define MAXN 100005 #define Mod 10001 using namespace std; int vis[10],n,ans,num[10]; int getsum(int l,int r) { int sum=0; for(int i=l; i<=r; ++i) sum=sum*10+num[i]; return sum; } void check() { for(int i=1; i<=9; ++i) { int a=getsum(1,i); if(a>n) continue; for(int j=i+1; j<9; ++j) { int b=getsum(i+1,j); int c=getsum(j+1,9); if(b>=c&&b%c==0&&a+b/c==n) { //cout<<a<<" "<<b<<" "<<c<<endl; ans++; } } } } void dfs(int step) { if(step==10) check(); else { for(int i=1; i<=9; ++i) { if(!vis[i]) { num[step]=i; vis[i]=1; dfs(step+1); vis[i]=0; } } } } int main() { scanf("%d",&n); ans=0; memset(vis,0,sizeof(vis)); dfs(1); printf("%d\n",ans); return 0; }