石油大--2020年秋季组队训练赛第十三场---- F、Historical Maths（二分）

题面：

题意：
给定三个数 $A,B,C$
每个数以以下的形式给出。
先给出一个正整数 $n$，表示这个数有 $n$ 位，然后给出 $n$ 个十进制非负整数，表示该数从高位到低位每个数位上的数的十进制表示。

若在某一进制下 $A\ast B=C$，输出符合要求的进制。

题解：
考虑当前 $k$ 进制下，如果 $A\ast B>C$ ，那么说明 $k$ 进制较小，$A\ast B$ 产生了较多的进位，说明符合要求的进制要比 $k$ 大。如果 $A\ast B<C$ ，那么说明 $k$ 进制较大，$A\ast B$ 产生了较少的进位（需要更多的进位才能达到 C 的值），说明符合要求的进制要比 $k$ 小。
如果 $A\ast B=C$ 那么说明当前 $k$ 进制符合要求。

代码：

#pragma GCC optimize(2)
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
namespace onlyzhao
{#define ui unsigned int#define ll __int128#define llu unsigned ll#define ld long double#define pr make_pair#define pb push_back//#define lc (cnt<<1)//#define rc (cnt<<1|1)#define len(x)  (t[(x)].r-t[(x)].l+1)#define tmid ((l+r)>>1)#define fhead(x) for(int i=head[(x)];i;i=nt[i])#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)>(y)?(y):(x))#define one(n) for(int i=1;i<=(n);i++)#define rone(n) for(int i=(n);i>=1;i--)#define fone(i,x,n) for(int i=(x);i<=(n);i++)#define frone(i,n,x) for(int i=(n);i>=(x);i--)#define fonk(i,x,n,k) for(int i=(x);i<=(n);i+=(k))#define fronk(i,n,x,k) for(int i=(n);i>=(x);i-=(k))#define two(n,m) for(int i=1;i<=(n);i++) for(int j=1;j<=(m);j++)#define ftwo(i,n,j,m) for(int i=1;i<=(n);i++) for(int j=1;j<=(m);j++)#define fvc(vc) for(int i=0;i<vc.size();i++)#define frvc(vc) for(int i=vc.size()-1;i>=0;i--)#define forvc(i,vc) for(int i=0;i<vc.size();i++)#define forrvc(i,vc) for(int i=vc.size()-1;i>=0;i--)#define cls(a) memset(a,0,sizeof(a))#define cls1(a) memset(a,-1,sizeof(a))#define clsmax(a) memset(a,0x3f,sizeof(a))#define clsmin(a) memset(a,0x80,sizeof(a))#define cln(a,num) memset(a,0,sizeof(a[0])*num)#define cln1(a,num) memset(a,-1,sizeof(a[0])*num)#define clnmax(a,num) memset(a,0x3f,sizeof(a[0])*num)#define clnmin(a,num) memset(a,0x80,sizeof(a[0])*num)#define sc(x) scanf("%d",&x)#define sc2(x,y) scanf("%d%d",&x,&y)#define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define scl(x) scanf("%lld",&x)#define scl2(x,y) scanf("%lld%lld",&x,&y)#define scl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)#define scf(x) scanf("%lf",&x)#define scf2(x,y) scanf("%lf%lf",&x,&y)#define scf3(x,y,z) scanf("%lf%lf%lf",&x,&y,&z)#define scs(x) scanf("%s",x+1)#define scs0(x) scanf("%s",x)#define scline(x) scanf("%[^\n]%*c",x+1)#define scline0(x) scanf("%[^\n]%*c",x)#define pcc(x) putchar(x)#define pc(x) printf("%d\n",x)#define pc2(x,y) printf("%d %d\n",x,y)#define pc3(x,y,z) printf("%d %d %d\n",x,y,z)#define pck(x) printf("%d ",x)#define pcl(x) printf("%lld\n",x)#define pcl2(x,y) printf("%lld %lld\n",x,y)#define pcl3(x,y,z) printf("%lld %lld %d\n",x,y,z)#define pclk(x) printf("%lld ",x)#define pcf2(x) printf("%.2f\n",x)#define pcf6(x) printf("%.6f\n",x)#define pcf8(x) printf("%.8f\n",x)#define pcs(x) printf("%s\n",x+1)#define pcs0(x) printf("%s\n",x)#define pcline(x) printf("%d**********\n",x)#define casett int tt;sc(tt);int pp=0;while(tt--)char buffer[100001],*S,*T;inline char Get_Char(){if (S==T){T=(S=buffer)+fread(buffer,1,100001,stdin);if (S==T) return EOF;}return *S++;}inline int read(){char c;int re=0;for(c=Get_Char();c<'0'||c>'9';c=Get_Char());while(c>='0'&&c<='9') re=re*10+(c-'0'),c=Get_Char();return re;}
};
using namespace onlyzhao;
using namespace std;const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e9;
const int mod=998244353;
const double eps=1e-9;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=2100;
const int maxm=100100;
const int up=100100;ll a[maxn],b[maxn],c[maxn];
ll tab[maxn];
int la,lb,lc;int check(int len1,int len2=lc)
{if(len1>len2) return 1;else if(len1<len2) return -1;for(int i=len1;i>=0;i--){if(tab[i]>c[i]) return 1;else if(tab[i]<c[i]) return -1;}return 0;
}int check(ll mid)
{memset(tab,0,sizeof(tab));for(int i=0;i<=la;i++){for(int j=0;j<=lb;j++)tab[i+j]+=a[i]*b[j];}for(int i=0;i<=la+lb;i++){tab[i+1]+=tab[i]/mid;tab[i]%=mid;}int cnt1=0;if(tab[la+lb+1]!=0) cnt1=la+lb+1;else cnt1=la+lb;while(tab[cnt1]>=mid){tab[cnt1+1]+=tab[cnt1]/mid;tab[cnt1]%=mid;cnt1++;}return check(cnt1);
}void print(ll ans)
{if(ans==0) return ;print(ans/10);printf("%d",(int)(ans%10));
}int main(void)
{ll max1=0;long long xx;scanf("%d",&la);la--;for(int i=0;i<=la;i++){scanf("%lld",&xx),max1=max(max1,xx+1);a[la-i]=xx;}scanf("%d",&lb);lb--;for(int i=0;i<=lb;i++){scanf("%lld",&xx),max1=max(max1,xx+1);b[lb-i]=xx;}scanf("%d",&lc);lc--;for(int i=0;i<=lc;i++){scanf("%lld",&xx),max1=max(max1,xx+1);c[lc-i]=xx;}ll maxx=0;for(int i=0;i<=la;i++){for(int j=0;j<=lb;j++)tab[i+j]+=a[i]*b[j];}for(int i=0;i<=la+lb;i++)maxx=max(maxx,tab[i]+1),maxx=max(maxx,max1);bool flag=false;ll ans=0;ll l=max1,r=maxx;ll mid=0;while(l<=r){mid=(l+r)>>1;int id=check(mid);if(id==1) l=mid+1;else if(id==-1) r=mid-1;else{flag=true;ans=mid;break;}}if(flag==false) printf("impossible\n");else print(ans);//ans != 0return 0;
}