題面
洛谷
題解
考場上半個小時就會做了,一個小時就寫完了。。
然後發現沒過樣例,結果大力調發現中間值爆 longlong l o n g l o n g 了,然後就沒管了。。
然後又沒切掉。。。我是真的傻逼。。。
首先每次選擇的刀一定,直接一個 multiset m u l t i s e t 就算出來了。
然後對于每關都單獨解一個方程
atk[i]x+p[i]y=a[i] a t k [ i ] x + p [ i ] y = a [ i ] ,直接 exgcd e x g c d 求解即可。
但是注意題目方程的含義,是以 x>0,y≤0 x > 0 , y ≤ 0
是以要解出來之後還需要額外的計算一下(就是這裡可能爆 ll l l …)
那麼此時對于每一個方程,我們都得到了一個最小的通解 X0[i] X 0 [ i ]
那麼,一個可行解 X=X0[i]+kd[i] X = X 0 [ i ] + k d [ i ] ,其中 d[i]=p[i]/gcd(p[i],atk[i]) d [ i ] = p [ i ] / g c d ( p [ i ] , a t k [ i ] ) , k k 是常數。
考慮如何合并兩個解,
X0[1]+k1d[1]=X0[2]+k2d[2]X0[1]+k1d[1]=X0[2]+k2d[2]
不妨令 X0[2]>X0[1] X 0 [ 2 ] > X 0 [ 1 ] ,移項得
X0[2]−X0[1]=k1d[1]+k2d[2] X 0 [ 2 ] − X 0 [ 1 ] = k 1 d [ 1 ] + k 2 d [ 2 ]
還是一個 exgcd e x g c d ,同時 k1≥0,k2≤0 k 1 ≥ 0 , k 2 ≤ 0 ,還是這裡額外算一下,中間值可能爆 ll l l
然後就可以算出這兩個方程合并後的最小特解 X0 X 0 ,
那麼這兩個方程合并後的通解就成了 X=X0+lcm(d[1],d[2]) X = X 0 + l c m ( d [ 1 ] , d [ 2 ] )
這樣子順次合并就行了。
至于中間值爆 ll l l 的問題,發現額外計算一下的過程就是一個取模+減法
是以龜速乘解決就好了。
然後無解就是某一步的時候 exgcd e x g c d 無解,直接判就好。
為啥他們都說是拓展CRT,我怎麼不知道啊???
這題我的代碼寫得好亂啊
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
using namespace std;
#define ll long long
#define MAX 100100
inline ll read()
{
ll x=;bool fl=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')fl=true,ch=getchar();
while(ch>='0'&&ch<='9')x=x*+ch-,ch=getchar();
return fl?-x:x;
}
int n,m;
ll a[MAX],p[MAX],g[MAX],atk[MAX];
ll LCM(ll a,ll b){return (a/__gcd(a,b))*b;}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==){x=;y=;return a;}
ll d=exgcd(b,a%b,y,x);
y-=a/b*x;return d;
}
namespace Choose
{
multiset<ll> S;
multiset<ll>::iterator it,itt;
void Work()
{
for(int i=;i<=n;++i)
{
it=itt=S.upper_bound(a[i]);
if(it!=S.begin())--itt,atk[i]=*itt,S.erase(itt);
else atk[i]=*it,S.erase(it);
S.insert(g[i]);
}
}
}
ll X0[MAX],d[MAX];
void init()
{
Choose::S.clear();
memset(a,,sizeof(a));memset(atk,,sizeof(atk));
memset(g,,sizeof(g));memset(p,,sizeof(p));
memset(X0,,sizeof(X0));memset(d,,sizeof(d));
}
ll Multi(ll a,ll b,ll p)
{
ll s=;
while(b){if(b&)s=(s+a)%p;a=(a+a)%p;b>>=;}
return (s+p)%p;
}
bool Solve()
{
ll x,y;
for(int i=;i<=n;++i)
{
ll D=__gcd(atk[i],p[i]),t,G,bs;
if(a[i]%D)return false;
exgcd(atk[i]/D,p[i]/D,x,y);
G=p[i]/D;t=Multi(x,a[i]/D,G);
if(t==)t+=G;
x=t;y=(a[i]-atk[i]*x)/p[i];
if(y>)
{
t=-y;G=atk[i]/D;
t=(t%G+G)%G;bs=(t+y)/G;
y=-t;x+=bs*(p[i]/D);
}
X0[i]=x,d[i]=p[i]/D;
}
for(int i=;i<=n;++i)
{
if(X0[i]<X0[i-])swap(X0[i],X0[i-]),swap(d[i],d[i-]);
ll c=X0[i]-X0[i-],D=__gcd(d[i],d[i-]),G,t,bs;
if(c%D!=)return false;
exgcd(d[i-]/D,d[i]/D,x,y);
G=d[i]/D;t=Multi(x,c/D,G);
x=t;y=(c-x*d[i-])/d[i];
if(y>)
{
t=-y;G=d[i-]/D;
t=(t%G+G)%G;bs=(t+y)/D;
y=t;x+=bs*(d[i]/D);
}
X0[i]-=d[i]*y;d[i]=LCM(d[i],d[i-]);
}
return true;
}
int main()
{
freopen("dragon.in","r",stdin);
freopen("dragon.out","w",stdout);
int T=read();
while(T--)
{
init();
n=read();m=read();
for(int i=;i<=n;++i)a[i]=read();
for(int i=;i<=n;++i)p[i]=read();
for(int i=;i<=n;++i)g[i]=read();
for(int i=;i<=m;++i)Choose::S.insert(read());
Choose::Work();
if(!Solve())puts("-1");
else printf("%lld\n",X0[n]);
}
return ;
}