#693890 (C) No.1544 [Cherry 2nd Tune C] Synchroscope

• 問題: No.1544 [Cherry 2nd Tune C] Synchroscope
• ユーザー: pengin_2000
• 提出日時: 2021-08-29 01:44:35
• 言語: C (gcc 12.3.0)
• 結果: WA
• 実行時間: -
• コード長: 1,115 bytes
• コンパイル時間: 1,362 ms
• コンパイル使用メモリ: 31,104 KB
• 実行使用メモリ: 6,824 KB
• 最終ジャッジ日時: 2024-11-22 01:26:34
• 合計ジャッジ時間: 3,106 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	AC	11 ms; 5,248 KB
testcase_07	WA	-
testcase_08	WA	-
testcase_09	AC	2 ms; 5,248 KB
testcase_10	AC	11 ms; 5,248 KB
testcase_11	WA	-
testcase_12	AC	6 ms; 5,248 KB
testcase_13	AC	2 ms; 5,248 KB
testcase_14	AC	14 ms; 5,248 KB
testcase_15	AC	16 ms; 5,248 KB
testcase_16	AC	6 ms; 5,248 KB
testcase_17	AC	4 ms; 5,248 KB
testcase_18	WA	-
testcase_19	WA	-
testcase_20	AC	14 ms; 5,248 KB
testcase_21	WA	-
testcase_22	AC	2 ms; 5,248 KB
testcase_23	AC	21 ms; 5,248 KB
testcase_24	AC	21 ms; 5,248 KB
testcase_25	AC	21 ms; 5,248 KB
testcase_26	AC	21 ms; 5,248 KB
testcase_27	AC	21 ms; 5,248 KB
testcase_28	AC	21 ms; 5,248 KB
testcase_29	AC	21 ms; 5,248 KB
testcase_30	AC	21 ms; 5,248 KB
testcase_31	AC	21 ms; 5,248 KB
testcase_32	AC	21 ms; 5,248 KB
testcase_33	AC	148 ms; 5,248 KB
testcase_34	AC	1 ms; 5,248 KB
testcase_35	AC	1 ms; 5,248 KB
testcase_36	AC	1 ms; 5,248 KB
testcase_37	AC	1 ms; 5,248 KB
testcase_38	WA	-
testcase_39	AC	20 ms; 5,248 KB
testcase_40	WA	-
testcase_41	AC	21 ms; 5,248 KB
testcase_42	AC	21 ms; 5,248 KB
testcase_43	WA	-
testcase_44	WA	-
testcase_45	AC	21 ms; 5,248 KB
testcase_46	AC	20 ms; 5,248 KB
testcase_47	WA	-

ソースコード

#include<stdio.h>
long long int gcd(long long int a, long long int b)
{
	long long int r = a % b;
	while (r > 0)
	{
		a = b;
		b = r;
		r = a % b;
	}
	return b;
}
long long int eu(long long int a, long long int b)
{
	if (b == 1)
		return 0;
	else
		return (1 - b * eu(b, a % b)) / (a % b);
}
int main()
{
	long long int n, m;
	scanf("%lld %lld", &n, &m);
	long long int i, j;
	int a[5003], b[5003];
	for (i = 0; i < n; i++)
		scanf("%d", &a[i]);
	for (j = 0; j < m; j++)
		scanf("%d", &b[j]);
	long long int ans = -2, g = gcd(n, m);
	long long int x, y;
	long long int k;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
		{
			if (a[i] != b[j])
				continue;
			if ((j - i) % g != 0)
				continue;
			x = eu(n / g, m / g);
			y = (1 - n / g * x) / (m / g);
			y *= -1;
			x *= (j - i) / g;
			y *= (j - i) / g;
			k = 0;
			if (x < 0)
				k = (-x + m / g - 1) / (m / g);
			if (y < 0)
			{
				if (k < (-y + n / g - 1) / (n / g))
					k = (-y + n / g - 1) / (n / g);
			}
			x += m / g * k;
			y += n / g * k;
			if (ans<0 || ans>x * n + i)
				ans = x * n + i;
		}
	}
	printf("%lld\n", ans + 1);
	return 0;
}