不枚不知道,一枚吓一跳,ma一堆数据超时

当然,用方程优化的代码不会超时

暴力找超时数据的代码

#include<bits/stdc++.h>
#define N 10005
#define INF 1145141LL
#define int long long
using namespace std;
int deep,flag;
int num[N];
int save[N];
int last,now;
timeb nt;
int lcm(int x,int y)
{
	return x*y/__gcd(x,y);
}
struct fs//分数结构体 
{
	int fz,fm;
	fs operator - (const fs x)const
	{
		int g=lcm(fm,x.fm);
		int f_a=g/fm*fz;
		int f_b=g/x.fm*x.fz;
		return {f_a-f_b,g};
	}
	void hj()
	{
		int g=__gcd(fz,fm);
		fz/=g,fm/=g;
	}
	bool operator < (const fs x)const
	{
		return fm<x.fm;
	}
};
void dfs(int x,fs f)
{
	ftime(&nt);
	now=nt.time*1000+nt.millitm;
	if(now-last>=1100)
		return;
	if(x>deep)return;
	if(f.fz==0)
	{
		if(num[x]>save[x] && flag)return;
		for(int i=1;i<=x;i++)
			save[i]=num[i];
		flag=1;
		return;
	}
	int l=max(f.fm/f.fz,num[x]+1);
	int r=min((deep-x)*f.fm/f.fz,(int)1e7);
	for(int i=l;i<=r;i++)
	{
		fs n_fs=f-((fs){1,i});
		if(n_fs.fz<0)continue;
		n_fs.hj();
		num[x+1]=i;
		dfs(x+1,n_fs);
	}
}
int vis[1005][1005];
signed main()
{
	for(int i=1;i<1000;i++)
	{
		for(int j=i+1;j<1000;j++)
		{
			fs a;
			a.fz=i,a.fm=j;
			a.hj();
			if(vis[a.fz][a.fm]==1)continue;
			vis[a.fz][a.fm]=1;
			num[0]=1;
			deep=1,flag=0;
			timeb lt;
			ftime(&lt);
			last=lt.time*1000+lt.millitm;
			while(++deep<10 && !flag)dfs(0,a);
			if(now-last>=1000)
				cout<<"输入为: "<<i<<" "<<j<<" 的数据可能超时\n";
		}
		cout<<"分子为"<<i<<"的枚举结束"<<"\n";
	}
	return 0;
}