求出 \(p\) 的原根 \(g\)，对每个 \(a_i\) 求出一个 \(x_i\) 表示 \(g^{x_i} \equiv a_i \pmod {p}\)（这部分可以 BSGS）。之后的表述中 \(a_i\) 指 \(x_i\)。那么集合生成方式相当于初始 \(c = 0\)，每次让 \(c \gets (c + a_i b_j) \bmod (p - 1)\)。
根据裴蜀定理，若求出 \(x\) 为所有 \(b_j\) 的 \(\gcd\)，每次操作相当于让 \(c \gets (c + x a_i) \bmod (p - 1)\)。
设 \(y_i = \gcd(x a_i, p - 1)\)，那么第 \(i\) 个集合就是 \(\le p - 1\) 且为 \(y_i\) 倍数的所有数（包括 \(0\)）。
现在要求集合并集大小。注意到 \(y_i\) 为 \(p - 1\) 的因数，于是对于 \(p - 1\) 的第 \(i\) 个因数 \(d_i\)，设 \(f_i\) 为集合并集中与 \(p - 1\) 的 \(\gcd = i\) 的数的个数，再求出是否存在一个 \(y_i\) 使得 \(d_i \mid y_i\)。若不存在则 \(f_i = 0\)；若存在则 \(f_i = \frac{p - 1}{d_i} - \sum\limits_{d_i \mid d_j} f_j\)。
那么答案就是 \(\sum f_i\)。
时间复杂度 \(O(\sqrt{np} + d(p - 1)^2)\)（前者是求 \(x_i\) 的复杂度；实际上后者的 \(O(d(p - 1)^2)\) 应该能做到 \(O(d(p - 1) \omega(p - 1))\)）。
code
// Problem: D. Levko and Sets
// Contest: Codeforces - Codeforces Round 210 (Div. 1)
// URL: https://codeforces.com/problemset/problem/360/D
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 100100;
const int maxm = 3200000;
ll n, m, mod, a[maxn], b[maxn], d[maxn], tot, f[maxn];
bool vis[maxn];
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
inline bool check(int x) {
vector<int> vc;
int t = mod - 1;
for (int i = 2; i * i <= t; ++i) {
if (t % i == 0) {
vc.pb(i);
while (t % i == 0) {
t /= i;
}
}
}
if (t > 1) {
vc.pb(t);
}
for (int y : vc) {
if (qpow(x, (mod - 1) / y) == 1) {
return 0;
}
}
return 1;
}
const int P = 333331;
struct HashTable {
int hd[P + 3], len, to[maxm], nxt[maxm], val[maxm];
inline void add(int x, int y) {
int u = x % P;
for (int i = hd[u]; i; i = nxt[i]) {
if (to[i] == x) {
return;
}
}
to[++len] = x;
val[len] = y;
nxt[len] = hd[u];
hd[u] = len;
}
inline int find(int x) {
int u = x % P;
for (int i = hd[u]; i; i = nxt[i]) {
if (to[i] == x) {
return val[i];
}
}
return -1;
}
} mp;
void solve() {
scanf("%lld%lld%lld", &n, &m, &mod);
if (mod == 3) {
puts("1");
return;
}
int g = 2;
while (!check(g)) {
++g;
}
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
ll x = mod - 1;
for (int i = 1; i <= m; ++i) {
scanf("%lld", &b[i]);
x = __gcd(x, b[i]);
}
ll pg = qpow(g, 316);
for (int i = 0, j = 1; i <= 3170000; ++i, j = j * pg % mod) {
mp.add(j, i);
}
for (int i = 1; i * i < mod; ++i) {
if ((mod - 1) % i) {
continue;
}
d[++tot] = i;
if (i * i != (mod - 1)) {
d[++tot] = (mod - 1) / i;
}
}
sort(d + 1, d + tot + 1);
for (int i = 1; i <= n; ++i) {
int j = 2e9;
for (int k = 0, p = a[i]; k <= 317; ++k, p = 1LL * p * g % mod) {
int t = mp.find(p);
if (t != -1 && t * 316 - k >= 0) {
j = min(j, t * 316 - k);
}
}
ll y = __gcd(x * j, mod - 1);
int t = lower_bound(d + 1, d + tot + 1, y) - d;
vis[t] = 1;
}
for (int i = 1; i <= tot; ++i) {
if (vis[i]) {
for (int j = i + 1; j <= tot; ++j) {
if (d[j] % d[i] == 0) {
vis[j] = 1;
}
}
}
}
ll ans = 0;
for (int i = tot; i; --i) {
if (!vis[i]) {
continue;
}
f[i] = (mod - 1) / d[i];
for (int j = i + 1; j <= tot; ++j) {
if (d[j] % d[i] == 0) {
f[i] -= f[j];
}
}
ans += f[i];
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}