結果

問題 No.3461 Min GCD
コンテスト
ユーザー 👑 tails
提出日時 2026-03-03 15:57:37
言語 cLay
(20250308-1 + boost 1.89.0)
コンパイル:
clayc _filename_
実行:
./a.out
結果
AC  
実行時間 410 ms / 2,000 ms
コード長 383 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,339 ms
コンパイル使用メモリ 240,368 KB
実行使用メモリ 213,048 KB
最終ジャッジ日時 2026-03-03 15:57:52
合計ジャッジ時間 8,684 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

//working_memory=128MB

int @n;
ll @k;
int @a[n],@b[n];
ull c[n*128+1];
int cn=0;

rep(i,n){
	ll d[128],e[128];
	int dn=Divisor(a[i],d);
	rep(j,dn){
		e[j]=(-b[i])%%d[j];
	}
	ll t=e[dn-1];
	k-=t;
	rrep(j,dn-1){
		if(t>e[j]){
			c[cn++]=(ull)d[j]<<32|t-e[j];
			t=e[j];
		}
	}
}

sortA(cn,c);
c[cn]=(ll)int_inf<<32;

while(k<0){
	ull v=c[--cn];
	k+=(int)v;
}

wt(min(c[cn]>>32,a(n)));
0