求助
查看原帖
求助
556362
Unnamed114514楼主2022/2/18 19:02
#include<bits/stdc++.h>
using namespace std;
inline int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}
#define F(a,b) F({a,b})
inline int read(){
	int res=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9'){
		res=(res<<1)+(res<<3)+(ch^'0');
		ch=getchar();
	}
	return res;
}
struct F{
	int a,b;
	inline F operator+(const F &t) const{
		int qwq=a*t.b+t.a*b,qaq=b*t.b;
		int awa=gcd(qwq,qaq);
		return F(qwq/awa,qaq/awa);
	}
	inline F operator-(const F &t) const{ return F(a,b)+F(-t.a,t.b);}
	inline bool operator>(const F &t) const{ return a*t.b>t.a*b;}
	inline bool operator!=(const F &t) const{ return a*t.b!=t.a*b;}
	inline bool operator==(const F &t) const{ return a*t.b==t.a*b;}
	inline void r(){ a=read(),b=read();}
}x;
int ans,xzj[105],a[10];
bool V[1005];
bool dfs(int a,F b,int c,int d){
	if(b>x||c+(b!=x)>a||c>=a)
		return 0;
	if(b==x)
		return 1;
	F qwq=x-b;
	if(c==a-1){
		if(qwq.a^1||qwq.b<=d||(qwq.b>xzj[c]&&xzj[c])||(qwq.b<=1000&&V[qwq.b]))
			return 0;
		xzj[c]=qwq.b;
		return 1;
	} else{
		bool flag=0;
		for(int i=d+1;F(a-c+1,i)>qwq;++i)
			if((i>1000||!V[i])&&dfs(a,b+F(1,i),c+1,i)){
			    xzj[c]=i;
			    flag=1;
			}
		return flag;
	}
}
signed main(){
	int T=read();
	for(int i=1;i<=T;++i){
		x.r();
		int k=read();
		for(int i=0;i<ans;++i)
			xzj[i]=0;
		for(int i=1;i<=k;++i){
			a[i]=read();
			V[a[i]]=1;
		}
		for(int i=1;;++i)
			if(dfs(i,F(0,1),0,0)){
				ans=i;
				break;
			}
		printf("Case %d: %d/%d=1/%d",i,x.a,x.b,xzj[0]);
		for(int i=1;i<ans;++i)
			printf("+1/%d",xzj[i]);
		putchar('\n');
		for(int i=1;i<=k;++i)
			V[a[i]]=0;
	}
	return 0;
}
2022/2/18 19:02
加载中...