[蓝桥杯 2013 省 B] 带分数

题目描述

$100$ 可以表示为带分数的形式：100=3+69258714100 = 3 + \\frac{69258}{714}100=3+71469258​。

还可以表示为：100=82+3546197100 = 82 + \\frac{3546}{197}100=82+1973546​。

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

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

输入格式

从标准输入读入一个正整数 N(N<106)N(N<10^6)N(N<106)。

输出格式

程序输出数字 $N$ 用数码 $1$ ~ $9$ 不重复不遗漏地组成带分数表示的全部种数。

注意：不要求输出每个表示，只统计有多少表示法！

样例 #1

样例输入 #1

100

样例输出 #1

11

样例 #2

样例输入 #2

105

样例输出 #2

6

提示

原题时限 3 秒, 64M。蓝桥杯 2013 年第四届省赛

#include<iostream>
#include<algorithm>
using namespace std;
int xu[11]{0,1,2,3,4,5,6,7,8,9};
int make_number(int x,int y){//将每一个数字拼起来 int yi=0;for(int i=x;i<=y;i++){yi*=10; yi+=xu[i];}return yi;
}
int main(){int n,ans=0;cin>>n;do{for(int i=1;i<=7;i++){//第一个数最多有7位 for(int j=i+1;j<=8;j++){//第二个数和第一个数的位数和最多为8 int num1=make_number(1,i);int num2=make_number(i+1,j);int num3=make_number(j+1,9);//把全排列分成三个数if(num1+(num2/num3)==n&&(num2%num3==0)){//套入公式 ans++;}}}}while(next_permutation(xu+1,xu+10));//非常高级的省代码函数 cout<<ans;return 0;
}