10pts玄棺求条
查看原帖
10pts玄棺求条
1110209
Eater_Tree楼主2025/6/19 19:39

AC on #10

#include<bits/stdc++.h>
using namespace std;
int n,a0,b0;
int a[1001000],b[1001000],c[1001000],a1[1001000],c1[1001000],lena;
//a表示左手的乘积(a是正序,a1是倒序)
//b表示k个大臣左手的数字(倒序),c表示第k个大臣右手的数字(c是正序,c1是倒序) 
int ans[1001000],anslen;
struct node{
	int a,b;
}m[2000];
int cmp(node x,node y){
	return x.a*x.b<y.a*y.b;//贪心 
}
int main(){
	scanf("%d%d%d",&n,&a0,&b0);
	while(a0>0){
		a[lena++]=a0%10;
		a0/=10;
	}
	for(int i=1;i<=n;i++)
		scanf("%d%d",&m[i].a,&m[i].b);
	sort(m+1,m+1+n,cmp);
	for(int k=1;k<=n;k++){
		memset(a1,0,sizeof(a1));
		memset(c1,0,sizeof(c1));
		int d=0,len=lena,lenb=0;
		memset(c,0,sizeof(c));
		//----高精度除法(本蒟蒻只会正序做)----
		for(int i=0;i<len;i++){
			c[i]=(d*10+a[i])/m[k].b;
			d=(d*10+a[i])%m[k].b;
		}
		for(int i=0;i<len;i++) c1[i]=c[len-i-1];
		while(c1[len-1]==0&&len>1) len--;
		//--------------------------------
		//---------高精度加法算ans---------
		anslen=max(anslen,len);
		for(int i=0;i<anslen;i++){
			ans[i+1]+=(ans[i]+c1[i])/10;
			ans[i]=(ans[i]+c1[i])%10;
		}
		anslen++;
		while(ans[anslen-1]==0&&anslen>1) anslen--;
		//--------------------------------
		memset(c,0,sizeof(c));
		while(m[k].a>0){
			b[lenb++]=m[k].a%10;
			m[k].a/=10;
		}
		for(int i=0;i<lena;i++) a1[i]=a[lena-i-1];
		//-----------高精度乘法-----------
		for(int i=0;i<lena;i++){
			for(int j=0;j<lenb;j++){
				c[i+j]+=a1[i]*b[j];
				c[i+j+1]+=c[i+j]/10;
				c[i+j]%=10;
			}
		}
		lena=lena+lenb;
		while(c[lena-1]==0&&lena>1) lena--;
		//--------------------------------
		for(int i=0;i<lena;i++) a[i]=c[lena-i-1];
	}
	for(int i=anslen-1;i>=0;i--) printf("%d",ans[i]);
	return 0;
}
2025/6/19 19:39
加载中...