Codeforces 1501D - Two chandeliers

Codeforces 1501D - Two chandeliers

八月 04, 2021

题目描述

给定两个有限数列$a,b$​,每个数列里的数均不相同，但是两个数列可能含有一样的数。现在把两个数列循环排列并依次对应，问对应的数第$k$次不相同的位置是多少。

分析与解

虽然这仅仅是个解两个方程的同余方程组，但还是费了些周折。

很明显的思路就是我们二分答案最后的位置，然后检查该位置之前扣除对应数相等的位置量是否还大于等于$k$.所以问题关键在于求解第一次对应数相等的位置（在$lcm(n,m)$之前）

对于一个同时出现在两个数列中的数而言，记其在$a$数列中出现的位置为$x$,在$b$数列中出现的位置为$y$,那么其实这个位置就是

这个东西用扩展CRT求解即可。

具体而言：我们考虑

它可以写成

首先移项忽略正负（之后讲调整）

存在解的条件就是

然后我们通过扩展欧几里得求出

的一组解$(x_1,x_2)$

假设我们最后用$x_1$来得到原本要求得$x$

现在回头考虑忽略正负的那个式子，如果老老实实作差，应该是：

因此可知

由此可见，我们用扩展欧几里得求出来的$x_1$​​实际上是模$mod=\frac{a2}{d}$​​​意义下的，因此可以通过

1
x1=(x1%mod+mod)%mod

来使得$x_1$​​变成一个正数。

最后$x=a_1\cdot x_1\frac{b2-b1}{(a1,a2)}+b1$来得到$x$即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;
#define MAXN 500100
typedef long long LL;
int mread() {
	int ret=0,f=1;
	char c=getchar();
	while(c<'0' || c>'9') {
		if(c=='-')f=-1;
		c=getchar();
	}
	do {
		ret=ret*10+c-'0';
		c=getchar();
	} while('0'<=c && c<='9');
	return ret*f;
}
int n,m;
LL k;
int a[MAXN],b[MAXN];
int posa[MAXN<<1],posb[MAXN<<1];
LL lcm;
int gcd(int a,int b) {
	if(b==0)return a;
	return gcd(b,a%b);
}
int exgcd(int a,int b,int &x,int &y) {
//	printf("%d %d\n",a,b);
	if(b==0) {
		x=1;
		y=0;
		return a;
	}
	int ret;
	ret=exgcd(b,a%b,y,x);
	y-=(a/b)*x;
	return ret;
}
vector<LL> S;
bool check(LL t) {
	LL rem=t;
	for(auto x : S) {
		if(t>=x)
			rem-=(t-x)/lcm+1;  //作差周期！ 
	}
	return rem >= k;
}
int main() {
	int g,x,y,mod;
	LL t1;
	n=mread(),m=mread();
	scanf("%lld",&k);
	memset(posa,-1,sizeof(posa));
	memset(posb,-1,sizeof(posb));
	for(int i=1; i<=n; i++) {
		a[i]=mread();
		posa[a[i]]=i;
	}
	for(int i=1; i<=m; i++) {
		b[i]=mread();
		posb[b[i]]=i;
	}
	g=exgcd(n,m,x,y);
	lcm=1ll*n*m/g;
	mod=m/g;
	for(int i=1; i<=2*max(n,m); i++) {
		if(posa[i]!=-1 && posb[i]!=-1 && posa[i]%g==posb[i]%g) {
			t1=1ll*x*(posb[i]-posa[i])/g;
			t1=(t1%mod+mod) %mod;  //将x1调整到合理的正数
			t1=t1*1ll*n + posa[i];
			S.push_back(t1);
//			printf("%d %d %d %lld\n",i,posa[i],posb[i],t1);
		}
	}
	sort(S.begin(),S.end());
	LL lef=1,rig=1e18,mid,ans;
	while(lef<=rig) {
		mid=(lef+rig)>>1;
		if(check(mid)) {
			ans=mid;
			rig=mid-1;
		} else lef=mid+1;
	}
	printf("%lld\n",ans);
	return 0;
}