题目链接

loj#2721. 「NOI2018」屠龙勇士

题解

首先可以列出线性方程组

方程组转化为在模p意义下的同余方程

因为不保证pp 互素，考虑扩展中国剩余定理合并

方程组是带系数的，我们要做的是在%p意义下把系数除过去,（系数为atk[i])

(atk[i],p[i]) 不等于1时无逆元，此时仍可能有解

很显然无解的情况就是

瞎jb猜的，无解的话就是%p[i]意义下atk[i] != 0 ,a[i] = 0

考虑原方程式ai = atk{i] * x + p[i] * y

方程两边同除gcd（pi,atki）解不变此时atki,pi此时保证了atki与pi互素

若ai不能被整除也是无解的

反正也没有-1的情况....

扩展crt

着实被winXP下输出lld坑了一把....顺带被自己抄的splay坑了一把

/*

苟活者在淡红的血色中，会依稀看到微茫的希望

*/

#include<bits/stdc++.h>

using namespace std;

inline long long read() {

long long x;

scanf("%lld",&x);

return x;

}

int n,m;

#define LL long long

const int maxn = 500007;

LL a[maxn],p[maxn]; // x atk[i] = a[i] ( % p[i])

LL atk[maxn],tatk[maxn]; 

struct Splay {

	#define fa(x) T[x].fa

	#define ls(x) T[x].ch[0]

	#define rs(x) T[x].ch[1]

	#define root T[0].ch[1]

	struct node

	{

	    LL val,rev,siz,fa,ch[2];

	}T[maxn];

	LL tot;

	void clear() {

		tot = 0; root = 0;

		for(LL i = 1; i <= maxn; i++) T[i].val = T[i].rev = T[i].siz = T[i].fa = T[i].ch[0] = T[i].ch[1] = 0;

	}

	LL ident(LL x){return T[fa(x)].ch[0]==x?0:1;}

	void connect(LL x,LL fa,LL how){T[fa].ch[how]=x;T[x].fa=fa;}

	void update(LL x){T[x].siz=T[ls(x)].siz+T[rs(x)].siz+T[x].rev;}

	void rotate(LL x)

	{

	    LL Y=T[x].fa,R=T[Y].fa;

	    LL Yson=ident(x),Rson=ident(Y);

	    LL B=T[x].ch[Yson^1];

	    connect(B,Y,Yson);

	    connect(Y,x,Yson^1);

	    connect(x,R,Rson);

	    update(Y);update(x);

	}

	void splay(LL x,LL to)

	{

	    to=T[to].fa;

	    while(T[x].fa!=to)

	    {

	        if(T[fa(x)].fa==to) rotate(x);

	        else if(ident(x)==ident(fa(x))) rotate(fa(x)),rotate(x);

	        else rotate(x),rotate(x);

	    }

	}

	LL newnode(LL fa,LL val) {

	    T[++tot].fa=fa;

	    T[tot].val=val;

	    T[tot].rev=T[tot].siz=1;

	    return tot;

	}

	LL find(LL val)

	{

	    LL now=root;

	    while(1)

	    {

	        if(T[now].val==val) {splay(now,root);return now;}

	        LL nxt=T[now].val<val;

	        now=T[now].ch[nxt];

	    }

	}

	void insert(LL val)

	{

	    if(root==0) {root=newnode(0,val);return ;}

	    LL now=root;

	    while(1)

	    {

	        T[now].siz++;

	        if(T[now].val==val) {T[now].rev++;splay(now,root);return ;}

	        LL nxt=val<T[now].val?0:1;

	        if(!T[now].ch[nxt]) {T[now].ch[nxt]=newnode(now,val);splay(now,root);return ;}

	        now=T[now].ch[nxt];

	    }

	}

	void erase(LL val)

	{

	    LL now=find(val);

	    if(T[now].rev>1) {T[now].rev--;T[now].siz--;return ;}

	    else if(!ls(now)&&!rs(now)) {root=0;return ;}

	    else if(!ls(now)) {root=rs(now);T[rs(now)].fa=0;return ;}

	    LL left=ls(now);

	    while(rs(left)) left=rs(left);

	    splay(left,ls(now));

	    connect(rs(now),left,1);

	    connect(left,0,1);

	    //update(rs(now));

	    update(left);//

	}

	LL pre(LL val)

	{

	    LL now=root,ans=-1e13;

	    while(now)

	    {

	        if(T[now].val<=val) ans=max(ans,T[now].val);

	        LL nxt=val<=T[now].val?0:1;

	        now=T[now].ch[nxt];

	    }

 	    return ans == -1e13 ? -1 : ans;

	}

	LL nxt(LL val)

	{

	    LL now=root,ans=1e13;

	    while(now)

	    {

	        if(T[now].val>val) ans=min(ans,T[now].val);

	        LL nxt=val<T[now].val?0:1;

	        now=T[now].ch[nxt];

	    }

	    return ans;

	}

}Sp;

LL gcd(LL a,LL b) {return b == 0 ? a : gcd(b,a % b);}

LL exgcd(LL a,LL b,LL &x,LL &y) {

	if(b == 0) {x = 1,y = 0;return a; }

	LL ret = exgcd(b,a % b,x,y);

	LL tmp = x;x = y;y = tmp - (a / b) * y;

	return ret;

}

LL inv(LL a,LL b) {

	LL x,y;

	exgcd(a,b,x,y);

	while(x < 0) x += b;

	return x;

}

void work() {

	LL ans = 0;

	for(int i = 1;i <= n;++ i) {

		ans = std::max(ans,a[i] % atk[i] == 0 ? a[i] / atk[i] : a[i] / atk[i] + 1);

	}

	printf("%lld\n",ans);

}

LL M[maxn],C[maxn];

inline LL add(LL x,LL y,LL mod) { return x + y >= mod ? x + y - mod : x + y; }

LL mul(LL x,LL k,LL mod) {

	LL ret = 0 ;

	x %= mod;

	for(;k;k >>= 1,x = add(x,x,mod))

		if(k & 1) ret = add(ret,x,mod);

	return ret;

}

bool flag = false;

void init() {

	Sp.clear();

	n = read(),m = read();

	flag = false;

	//puts("haha");

	for(int i = 1;i <= n;++ i) a[i] = read();

	for(int i = 1;i <= n;++ i){ p[i] = read();if(p[i] != 1) flag = true; }

	for(int j = 1;j <= n;++ j) tatk[j] = read();

	//printf("%d %d %d\n",n,m,flag);

	for(int k,i = 1;i <= m;++ i)

		k = read(),Sp.insert(k);

	for(int i = 1;i <= n;++ i) {

		//puts("asdasd");

		LL p = Sp.pre(a[i]);

		if(p == -1) p = Sp.nxt(a[i]);

		atk[i] = p;

		Sp.erase(p);

		 Sp.insert(tatk[i]);

	}

	if(!flag) {work();/*puts("haha");*/return; }

	int num = 0;

	for(int i = 1;i <= n;++ i) {

		a[i] %= p[i],atk[i] %= p[i];

		if(!a[i] && !atk[i]) continue;

		else if(!atk[i]){puts("-1");return;}

		LL d = gcd(atk[i],p[i]);

		if(a[i] % d != 0) {continue; }

		a[i] /= d,atk[i] /= d,p[i] /= d;

		C[++ num] = mul(a[i] , ((inv(atk[i],p[i]) % p[i] + p[i]) % p[i]),p[i]);

		M[num] = p[i];

	}

	LL m = M[1],A = C[1],x,y,t;

	for(int i = 2;i <= num;++ i) {

		LL d = exgcd(m,M[i],x,y);

		t = (M[i] / d);

		//if((C[i]-A)%d == 0 || (a[i] - A) % d == -0 ) {

			x = mul((x % t + t) % t,(((C[i] - A) / d) % t + t) % t,t);

			LL MOD = (m / d) * (M[i]);

			A = (mul(m , x, MOD) + A % MOD) % MOD;

			m = MOD;

		// else {puts("-1"); return;};

	}

	A = (A % m + m) % m;

	printf("%lld\n",A);

} 

int main() {

	freopen("dragon.in","r",stdin); freopen("dragon.out","w",stdout);

	int t = read();

	while(t --) {

		init();

	}

	return 0;

}

巴特西

loj#2721. 「NOI2018」屠龙勇士

题目链接

题解

最新文章

热门文章