这道题做的我 七窍生烟 半死不活 怒斥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;
}