結果

問題 No.1350 2019-6problem
コンテスト
ユーザー ID 21712
提出日時 2026-05-26 18:54:11
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 705 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 11,291 ms
コンパイル使用メモリ 286,068 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-05-26 18:54:28
合計ジャッジ時間 12,479 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"
import . "math/big"
import . "sort"

func main() {
	var a,b,k int
	Scan(&a,&b,&k)
	gcd := int(new(Int).GCD(nil,nil,NewInt(int64(a)),NewInt(int64(b))).Int64())
	lcm := a*b/gcd
	
	ans := Search(min(a*k,b*k)+2, func(i int) bool {
		return i/a+i/b-i/lcm >= k
	})
	
	Println(ans)
}

/*
考察

AまたはBの倍数である正整数Nがあって
1～Nまでで
K = Aの倍数の個数 + Bの倍数の個数 - LCM(A,B)の倍数の個数
となるようなNを見つけろってこと？

Aの倍数がK個、小さいほうからK個目の値は A*K
Bの倍数がK個、小さいほうからK個目の値は B*K
で
N <= min(A*K,B*K)
が成り立つ

二分探索、だよね？

*/
0