这道题做的我 七窍生烟 半死不活 怒斥UVA无人性
明白了longlong 的重要性

题目大意

给一个真分数a/b,把他拆分成1/x1+1/x2+1/x3……

若有多种情况,输出拆分出分数最少的一种

如果还有多种情况,输出分母第一大最小,如果还不行,第二大最小,以此类推。

第一行输入数据组数 t

注意,每行输入这几个数 :

分子a 分母b 不能用的分母k个 然后后面会有k个不能用给的整数

解题过程

被卡了两个半小时,代码越来越题解化。

不过下面那个题解没说的太清楚,这里附上几个证明。

证明1. 分母下界取值

∵ a/b 为真分数 ,a,b,k均为整数

∴ a<b

设正整数x,y ax+y=b

发现 floor(b/a)=floor( (x a+y) /a )=floor(x a/a)+floor(y/a) = x

以及 floor(b/a)<=b/a

∴ floor(b/a)=x

∴ x+1 > b/a , ∴floor(b/a)+1>b/a

∴ 1/(x+1) < a/b 又 1/floor(b/a)=1/x >=a/b

∴ x+1就是最小的 k 使得 1/k < a/b

∴ k=floor(b/a) + 1

证明2. 分母上界取值

if(a i>=b (mmxdep-dep+1)) return ;

证明过程

a i >= b (mmxdep-dep+1)

a >= (b * mmxdep-dep+1)/i 两边除i

a/b >= (mmxdep-dep+1) /i 两边除b

a/b >= (1/i ) * (mmxdep-dep+1) 换一个等价写法

也就是说,剩下即使按照每一个分数都是比最大还大的i/1会留下,因此直接剪枝

通分的方式

这句话在通分: na=a i-b,nb=b i;

当前数值为a/b,我们要从中抽出1/i

原式 = a/b-1/i

  =ai/bi-b/bi

  =(ai-b)/bi

na存的是左边分子,nb存的是右边分母,这个过程相当于通分

我觉得应该差不多了,那就上代码吧

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
g#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<set>

#define re int //因为UVA毒瘤评测机,所以(可能)只能这么写

using namespace std;

long long n,t,k,mmxdep,f; //因为UVA毒瘤评测机,所以只能这么写
long long bs[100500],tmp[100500],mutia,mutib,w[100500];
//原来WA了一页,这里改成这样,为了保险就这样吧
set <long long> p;

int pd()
{
for(re i=mmxdep;i>=1;i--)
{
if(bs[i]!=w[i])
{
if(bs[i]==0) return 0;
if(bs[i]>w[i]) return 0;
return 1;
}
}
return 1;
}

long long gcd(long long a,long long b)
{
if(b==0) return a;
else return gcd(b,a%b);
}

void dfs(int dep,long long a,long long b,long long lasi)
{
long long i;
if(dep==mmxdep)
{
if(b%a||p.count(b/a)) return ;
w[dep]=b/a;
if(!pd()) memcpy(bs,w,sizeof(w));
//memcpy的用法 如果把A cpoy 到 B ,可以写为memcpy(B,A,sizeof(A))
f=1;
return ;
}
for(i=max(lasi,b/a+1);;i++)
{
if(p.count(i)) continue; //set的用法,检查i是否被标记,复杂度大概Log 2(N)
if(a*i>=b*(mmxdep-dep+1)) return ; //上面说的剪枝
long long na=a*i-b,nb=b*i;
long long fri=gcd(na,nb);
w[dep]=i;
dfs(dep+1,na/fri,nb/fri,i+1);
}
return ;
}

int main()
{
int i,j;
scanf("%lld",&t);
for(i=1;i<=t;i++)
{
long long t1;
p.clear();
scanf("%lld %lld %lld",&mutia,&mutib,&k);
for(j=1;j<=k;j++)
scanf("%lld",&t1),p.insert(t1);
for(mmxdep=2;;mmxdep++)
{
memset(bs,0,sizeof(bs));
dfs(1,mutia,mutib,mutib/mutia+1);
if(f) break;
}
printf("Case %d: %lld/%lld=1/%lld",i,mutia,mutib,bs[1]);
for(j=2;j<=mmxdep;j++)
printf("+1/%lld",bs[j]);
printf("\n");
memset(bs,0,sizeof(bs)); //每次完成后记得清零数组
f=0; //标记重置
}
return 0;
}