P8599 [蓝桥杯 2013 省 B] 带分数

题目描述

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

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

注意特征：带分数中，数字 11 ~ 99 分别出现且只出现一次（不包含 00）。

类似这样的带分数，100100 有 1111 种表示法。

输入格式

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

输出格式

程序输出数字 NN 用数码 11 ~ 99 不重复不遗漏地组成带分数表示的全部种数。

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

思路

把123456789全排列后的每种情况划分整数部分a，分子b，分母c，再判断是否与输入的正整数相等。

代码

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n;
 4 int ans;
 5 int a[10];
 6 int cc(int n,int m){
 7     int sum=0;
 8     int mult=1;
 9     for(int i=m;i>=n;i--){
10         sum += a[i]*mult;
11         mult *=10;
12     }
13     return sum;
14 }
15 void dfs(){
16     do{
17         for(int i=1;i<8;i++){
18             for(int j=i+1;j<9;j++){
19                 int a=cc(1,i);
20                 int b=cc(i+1,j);
21                 int c=cc(j+1,9);
22                 if(b== c*n -c*a)
23                     ans++;
24             }
25         }
26     }while(next_permutation(a+1,a+10));
27     return;
28 }
29 int main(){
30     cin >> n;
31     for(int i=1;i<=9;i++)
32         a[i]=i;
33     dfs();
34     cout << ans << endl;
35     return 0;
36 }