IDA*90TLEon9求助
查看原帖
IDA*90TLEon9求助
804759
oiler153楼主2023/6/21 18:17
#include<iostream>
using namespace std;
#define int long long
int p[10919810],tot,t[10919810];
inline int read() {
  int x = 0,f=1;
  char ch = 0;
  while (ch < '0' || ch > '9') { 
  	if(ch=='-')
  		f=-1;
    ch = getchar(); 
  }
  while (ch >= '0' && ch <= '9') { 
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x*f;
}
inline void write(int x) {
	static int sta[15];
  	int top = 0;
  	do {
  	  sta[top++] = x % 10, x /= 10;
  	} while (x);
  	while (top) putchar(sta[--top] + 48); 
  	putchar(' ');
}
struct fen{
	int zi,mu;
};
int gcd(int a,int b){
	if(b==0)
		return a;
	return gcd(b,a%b);
}
fen jian(fen a,fen b){
	fen temp;
	temp.mu=a.mu*b.mu;
	temp.zi=(a.zi*b.mu-a.mu*b.zi);
	if(a.zi!=0){	
		int k=gcd(temp.mu,temp.zi);
		temp.zi/=k,temp.mu/=k;
	}
	return temp;
}
void idax(fen a,int deep,int x){
	if(deep>tot){
		if(a.zi==0&&p[tot]<t[tot]){
			for(int i=1;i<=tot;i++){
				t[i]=p[i];
			}
		}
		return;
	}
	fen kk;
	kk.zi=1;
	int r=(a.mu*(tot-deep+1)+a.zi-1)/a.zi;
	if(r>10000000)
		r=10000000;
	int l=max(x+1,(a.mu+a.zi-1)/a.zi);
	for(int i=l;i<=r;i++){
		p[deep]=i;
		kk.mu=i;
		idax(jian(a,kk),deep+1,i);
	}
}
signed main(){
	//cout<<gcd(540,3)<<endl;
	fen k;
	k.zi=read(),k.mu=read();
	for(tot=1;1;tot++){
		t[tot]=0x3f3f3f;
		idax(k,1,1);
		if(t[tot]!=0x3f3f3f)
			break;
	}
	for(int i=1;i<=tot;i++)
		write(t[i]);
	return 0;
}
2023/6/21 18:17
加载中...