20 求调
查看原帖
20 求调
543779
ruoyu_楼主2024/10/24 20:13
#include<bits/stdc++.h>
using namespace std;
#define N 1000005
#define M 10000
int n,k,x,y,q;
int B[N],ans[N],lenb=1,lenc,lenans;
int C[N],D[N];
struct play{
	int l,r;
	int pro;
	friend bool operator <(play a,play b){return a.pro<b.pro;}
}A[N];
void cheng(int x){
	for(int i=1;i<=lenb;i++)
		B[i]*=A[x-1].l;
	for(int i=1;i<lenb;i++){
		if(B[i]>=M){
			B[i+1]+=B[i]/M;
			B[i]%=M;
		}
	}
	while(B[lenb]>=M){
		B[++lenb]=B[lenb-1]/M;
		B[lenb-1]%=M;
	}
}
void chu(int x){
	reverse(B+1,B+1+lenb);
	int y=0,q=1;
	for(int i=1;i<=lenb;i++){
		C[i]=(y*M+B[i])/A[x].r;
		y=(y*M+B[i])%A[x].r;
	}
	while(q<lenb&&C[q]==0)q++;
	lenc=lenb-q+1;
	for(int i=1;i<=lenc;i++)
		C[i]=C[q+i-1];
	reverse(B+1,B+1+lenb);
}
int main(){
	scanf("%d%d%d",&n,&x,&y);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&A[i].l,&A[i].r);
		A[i].pro=A[i].l*A[i].r;
	}
	sort(A+1,A+1+n);
	A[0].l=x;A[0].r=y;
	B[1]=1;
	for(int i=1;i<=n;i++){
		cheng(i);
		chu(i);
		if(lenans>lenc)continue;
		if(lenans<lenc||(lenans==lenc&&memcmp(ans,C,sizeof(ans))<0)){
			lenans=lenc;
			memcpy(ans,C,sizeof(C));
			continue;
		}
	}
	printf("%d",ans[1]);
	for(int i=2;i<=lenans;i++)
		printf("%04d",ans[i]);
    return 0;
}
2024/10/24 20:13
加载中...