結果

問題 No.3461 Min GCD
コンテスト
ユーザー 👑 tails
提出日時 2026-03-03 16:08:32
言語 cLay
(20250308-1 + boost 1.89.0)
コンパイル:
clayc _filename_
実行:
./a.out
結果
AC  
実行時間 89 ms / 2,000 ms
コード長 450 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 9,232 ms
コンパイル使用メモリ 241,280 KB
実行使用メモリ 112,852 KB
最終ジャッジ日時 2026-03-03 16:08:43
合計ジャッジ時間 8,899 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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;

if(sum[ll][i,0,n]((-b[i])%%a[i])<=k){
	wt(min(a(n)));
	exit(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