結果

問題 No.1544 [Cherry 2nd Tune C] Synchroscope
コンテスト
ユーザー pengin_2000
提出日時 2021-08-29 01:36:01
言語 C
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,166 bytes
コンパイル時間 2,006 ms
コンパイル使用メモリ 30,976 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-22 01:23:55
合計ジャッジ時間 2,555 ms
ジャッジサーバーID
（参考情報） 		judge4 / 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;
	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;
			if (x < 0)
			{
				y += n / g * (-x / (m / g));
				x %= m / g;
				if (x < 0)
				{
					x += m / g;
					y += n / g;
				}
			}
			if (y < 0)
			{
				x += m / g * (-y / (n / g));
				y %= n / g;
				if (y < 0)
				{
					x += m / g;
					y += n / g;
				}
			}
			if (ans<0 || ans>x * n + i)
				ans = x * n + i;
		}
	}
	printf("%lld\n", ans + 1);
	return 0;
}
0