Language: C++

#include<iostream>
#include<stdint>
using namespace std;

const int MAX = 50;
const int MAX2 = 2500;
const int64_t INF = 100000000000000000;

int64_t edge[MAX + 1][MAX + 1]; // edge[i][j]はiからjへ変更するコスト
int64_t cost[MAX]; // 各変更時コスト

void reset() {
	for (int i = 0;i <= MAX;i ++) {
		for (int j = 0;j <= MAX;j ++) {
			edge[i][j] = INF;
		}
		edge[i][i] = 0;
	}
}
void check() {
	for (int i = 1;i <= MAX;i ++) {
		for (int j = 1;j <= i;j ++) {
			if (edge[i][i % j] > edge[i][i] + cost[j - 1]) edge[i][i % j] = edge[i][i] + cost[j - 1]; // 経路コスト
		}
	}
}
void warshallFloyd() {
	for (int i = 0;i <= MAX;i ++) { // ワーシャルフロイド法
		for (int j = 0;j <= MAX;j ++) {
			for (int k = 0;k <= MAX;k ++) {
				if (edge[i][j] > edge[i][k] + edge[k][j]) edge[i][j] = edge[i][k] + edge[k][j];
			}
		}
	}
}

int get(int64_t n) {
	int ret = 0;
	while (n > 0) {
		ret ++;
		n >>= 1;
	}
	return ret;
}
int main() {
	int N, a[MAX2], b[MAX2], c[MAX];
	cin >> N;
	for (int i = 0;i < MAX2;i ++) a[i] = -1;
	for (int i = 0;i < N;i ++) cin >> a[i * MAX];
	for (int i = 0;i < N;i ++) cin >> b[i * MAX];
	for (int i = 0;i < MAX;i ++) c[i] = 0;
	for (int i = 0;i < N;i ++) c[i] = 1;
	
	for (int i = 0;i < MAX;i ++) cost[i] = (int64_t)1 << i + 1;
	int64_t finalCost = 0;
	for (int i = 0;i < MAX;i ++) {
		reset(); // O(N^2)
		check(); // O(N^2)
		warshallFloyd(); // O(N^3)
		int64_t bit = 0, tmp, tmp2;
		for (int j = 0;j < N;j ++) {
			tmp2 = INF;
			for (int k = 0;k < c[j];k ++) {
				if (edge[a[j * MAX + k]][b[j * MAX + k]] >= INF) continue;
				if (edge[a[j * MAX + k]][b[j * MAX + k]] == 0) tmp2 = -1;
				tmp = (int64_t)1 << (get(edge[a[j * MAX + k]][b[j * MAX + k]]) - 1);
				if (tmp2 > tmp) tmp2 = tmp;
			}
//			cout << tmp2 << endl;
			if (tmp2 < INF && tmp2 >= 0) bit |= tmp2;
			else if (tmp2 >= INF) {
				cout << -1;
				return 0;
			}
		}
		int maxBit = get(bit) - 1;
//		cout << "max:" << maxBit << endl;
		if (maxBit >= 0) {
			finalCost |= (int64_t)1 << maxBit;
			for (int j = 0;j < N;j ++) { // 数字更新
				for (int k = 0;k < c[j];k ++) {
					if (a[j * MAX + k] >= maxBit) {
						a[j * MAX + c[j]] = a[j * MAX + k] - maxBit;
						b[j * MAX + c[j]] = b[j * MAX + k];
						c[j] ++;
					}
				}
			}
		}
		bool endFlag = true; // 終了してたらtrue
		for (int j = 0;j < N;j ++) {
			bool endFlag2 = false;
			for (int k = 0;k < c[j];k ++) {
				endFlag2 |= a[j * MAX + k] == b[j * MAX + k];
			}
			endFlag &= endFlag2;
		}
		if (endFlag) {
			cout << finalCost;
			return 0;
		}
		cost[maxBit - 1] = 0;
	}
	// ここまででcostは必要な経路を抽出してるが、余分な経路がある可能性がある
	// なんでかは分からん！とりあえず更に検討するよー！
	// まず、ワーシャルフロイドの関係上、一番大きい経路を見落とした可能性はない
	// なのでこれは省く
	// じゃ、そこのコストを0、全てをそれで変換後にしたうえでもう一回ワーシャルフロイドとかどうだろう(脳死)
	// O(N^4)？あれ、通るじゃん
	
	
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり

まず、選ぶ要素はmax(b)+1以上max(a)以下であることは確実、そうでないと意味がない
また、割る順番で結果が変わるので慎重に選ぶ必要がある
ところで、Kが小さいので先に数字の移動先を計算しておくことはできるな？
例えば15 mod 7 → 1みたいなことは先に計算しておける
なら、下準備としてそれをやっておくことを考えてみよう

あれ、先にコストを計算したら後は最短経路問題だな？
ならワーシャルフロイド法で終了だ

さて、ここまでで使うべき経路が分かった……と思ったか？
他の経路と被る場合にそっち使った方が良いことがあるので更に検出
ぶっちゃけ答え分かってないから嘘解法とか言わない！
*/

Compiler output:
a.cc:2:9: fatal error: stdint: No such file or directory
    2 | #include<stdint>
      |         ^~~~~~~~
compilation terminated.