結果

問題 No.1544 [Cherry 2nd Tune C] Synchroscope
ユーザー pengin_2000
提出日時 2021-08-29 01:44:35
言語 C
(gcc 13.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 34 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0