带分数

问题描述

100 可以表示为带分数的形式：100 = 3 + 69258 / 714。

还可以表示为：100 = 82 + 3546 / 197。

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

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

输入格式

从标准输入读入一个正整数N (N<1000*1000)

输出格式

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

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

样例输入1

100

样例输出1

样例输入2

105

样例输出2

Algorithm

一开始，常规思路进行枚举，因为等式形如：

那么考虑整除的问题，C最多不超过4位数，A不超过7位数，由等式我们可以算出B。则过程很清晰了：

分别枚举A和C，算出B，判断一下是否满足条件，计数即可。

但是仔细分析了一下时间复杂度，果然没有通过。先放一下代码：

 1 /*
 2 * N = A + B/C
 3 * A最多7位，C最多4位,算出B 
 4 */
 5 #include<iostream>
 6 #include<algorithm>
 7  
 8 using namespace std;
 9 
10 int c = 0,N = 0;;
11 
12 // 获取数字长度 
13 int size(int n)
14 {
15     int c = 0;
16     while(n)
17     {
18         n /= 10;
19         c++;
20     }
21     return c;
22 }
23 
24 bool sure(int A, int B, int C)
25 {
26     // 排除有0项 
27     if((size(A) + size(B) + size(C)) != 9)
28         return false;
29     if(A == C)
30         return false;
31     if(B <= 0)
32         return false;
33     int s[10] = {0};
34     // int a=A,b=B,c=C;
35     while(A!=0 || B!=0 || C!=0)
36     {
37         s[A%10]++;s[B%10]++;s[C%10]++;
38         A /= 10;B /= 10;C /= 10;
39     }
40     for(int i=1;i<=9;i++){
41         if(s[i] != 1)
42             return false;
43     }
44     // cout<<a<<":"<<b<<":"<<c<<endl;
45     return true;
46 }
47 
48 int solve(int n)
49 {
50     // 设置循环节加速，但效果甚小
51     int len[7] = {0, 9876, 987, 987, 98, 98, 9};
52     int A = 1, C = 2, B = 0;
53     for(A=1;A<=9876543;A++){ // 需要排除有0的项 
54         // 在这里的几个ABC也可以排除0项，但效果也甚微
55         for(C=2;C<=len[size(A)];C++){
56             B = C*(N - A);
57             if(sure(A, B, C))
58                 c++;
59         }
60     }
61     return c;
62 }
63 /*
64 * 加速了还是发现时间复杂度太高，约O(9876543 * 5000)
65 * 改用全排列试试 约O(7 * 9!)
66 * 速度提升大约 70*30 倍
67 */
68 int main()
69 {
70     while(cin>>N)
71     {
72         cout<<solve(N)<<endl;
73         c = 0;
74     }
75     return 0;
76 }

View Code

但是思路是没有问题的，接下来想到了以前做过的一道题目：桥本分数式

基本与本题一致，所以改用全排列的做法。枚举9个数的全排列确实要比循环每一个A、C快得多。

全排列可以用C++自带的 #include<algorithm> 头文件的 next_permutation 函数。也可以深度优先遍历。

用一个数组保存1 -- 9之后，我们只需要尝试每一个组合的有限个分组即可，满足等式计数+1.

尽管还是有点吃力，但是勉强过了。

AC

 1 /*
 2 * N = A + B/C
 3 * A 最长不超过7位数, 这样我们确定一个 A 
 4 * 然后我们可以知道 C 的最后一位为 a[8]
 5 * 通过计算我们可以确定 B 的 最后一位 b_end = (N - A)*a[8]%10
 6 * 如此，我们就知道了 C 为多少
 7 * 最后，判断一下是否满足等式 
 8 */
 9 #include<iostream>
10 #include<algorithm>
11  
12 using namespace std;
13 
14 int c = 0,N = 0;;
15 int a[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
16 
17 // 这里复习一下整数快速幂，就不调用数学库了
18 // O(log2N)
19 int pow(int x, int n)
20 {
21     int s = 1;
22     while(n)
23     {
24         if(n&1) s *= x;
25         x *= x;
26         n >>= 1;
27     }
28     return s;
29 }
30 
31 // A、B、C, b开始, e-1结束的一段数组 
32 int PI(int b, int e)
33 {
34     int s = 0, k = e-b-1;
35     while(b!=e)
36     {
37         s += a[b]*pow(10, k);k--;b++;
38     }
39     return s;
40 }
41 
42 // 获取 B 最后一位的 local 
43 int getB_end(int x)
44 {
45     int loc = 0;
46     for(int i=0;i<9;i++)
47         if(a[i] == x)
48             return i;
49 }
50 
51 void solve(int *a, int N)
52 {
53     int A, B, C;A = B = C = 0;
54     // cout<<N<<endl;
55     for(int i=1;i<=7;i++){
56         A = PI(0, i);
57         int B_end = ((N - A)*a[8])%10;
58         int loc = getB_end(B_end);
59         if(loc < i || loc >= 8)
60             continue;
61         // Ai! 这里注意一下是 loc + 1 
62         B = PI(i, loc+1);
63         C = PI(loc+1, 9);    
64         // cout<<A<<":"<<B<<":"<<C<<endl;
65         // cout<<A<<":"<<B<<":"<<C<<endl;    
66         if(A*C + B == N*C){
67             // cout<<A<<":"<<B<<":"<<C<<endl;
68             c++;
69         }    
70     }
71 }
72 
73 int main()
74 {
75     while(cin>>N)
76     {
77         while(next_permutation(a, a+9))
78         {   // 时间复杂度可以看成 O(9!) 
79             solve(a, N);
80             // break;
81         }
82         cout<<c<<endl;c = 0;
83     }
84     return 0;
85 }

View Code

2019-01-15

19:09:38