我这有个玄学剪枝
  • 板块P1763 埃及分数
  • 楼主orgn
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/7/13 16:16
  • 上次更新2023/10/27 20:37:22
查看原帖
我这有个玄学剪枝
402384
orgn楼主2022/7/13 16:16
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll a,b,ans[10000005],cnt[10000005],tot=0,len=1;
ll gcd(ll a,ll b){
	if(b==0) return a;
	return gcd(b,a%b);
}
bool dfs(int y,ll c,ll d){
	if(d>10e7) return false;//玄学剪枝,毫无道理
	if(y==tot+1){
		if(c!=0) return false;
		if(ans[tot]>cnt[tot]) for(int i=1;i<=tot;i++) ans[i]=cnt[i],len=tot;
		return true;
	}
	bool flag=false;
	for(int i=max((int)cnt[y-1]+1,(int)ceil(d/c));i<=min(ceil(d/c)*(tot-y+1),1e7);i++){
		if(ans[len]<i) break;
		cnt[y]=i;
		if(dfs(y+1,(c*i-d)/gcd(c*i-d,d*i),(d*i)/gcd(c*i-d,d*i))) {
			flag=true;
		}
	}
	return flag;
}
int main () {
	cin>>a>>b;
	for(tot=1;;tot++){
		ans[tot]=0x3f3f3f3f;
		if(dfs(1,a,b)) break;
	}
	for(int j=1;j<=tot;j++) cout<<ans[j]<<" ";
	return 0;
}

就挺离谱的,我也不知道为啥是对的……

2022/7/13 16:16
加载中...