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
| #include <iostream>
#include <vector>
#define maxn 500010
#define ll long long
using namespace std;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int n, m, p1[maxn * 2], p2[maxn * 2];
ll k;
void exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) return x = 1, y = 0, void();
exgcd(b, a % b, y, x);
y -= x * (a / b);
}
ll t, g, l;
vector<ll> A;
bool check(ll x) {
ll s = x;
for (auto u : A)
s -= x / l + (x % l >= u);
return s >= k;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m >> k;
g = gcd(n, m); t = m / g; l = t * n;
for (int i = 1, x; i <= n; ++i) cin >> x, p1[x] = i;
for (int i = 1, x; i <= m; ++i) cin >> x, p2[x] = i;
for (int i = 1; i <= 2 * max(n, m); ++i) {
if (!p1[i] || !p2[i] || (p1[i] - p2[i]) % g) continue;
ll x, y; exgcd(n, m, x, y);
x *= (p2[i] - p1[i]) / g;
x = (x % t + t) % t;
A.push_back(p1[i] + n * x);
}
ll l = 1, r = 1000000000000000000ll, mid, ans;
while (l <= r) {
mid = l + r >> 1;
if (check(mid)) ans = mid, r = mid - 1;
else l = mid + 1;
} cout << ans << "\n";
return 0;
}
|