結果

問題 No.1611 Minimum Multiple with Double Divisors
ユーザー 小野寺健小野寺健
提出日時 2021-12-18 09:44:21
言語 Go
(1.22.1)
結果
TLE  
実行時間 -
コード長 1,049 bytes
コンパイル時間 14,784 ms
コンパイル使用メモリ 218,668 KB
実行使用メモリ 14,796 KB
最終ジャッジ日時 2024-09-15 10:15:52
合計ジャッジ時間 29,330 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,491 ms
12,008 KB
testcase_01 AC 532 ms
6,508 KB
testcase_02 AC 561 ms
6,508 KB
testcase_03 AC 561 ms
6,400 KB
testcase_04 AC 566 ms
6,512 KB
testcase_05 AC 561 ms
6,508 KB
testcase_06 AC 563 ms
6,508 KB
testcase_07 AC 560 ms
6,504 KB
testcase_08 AC 562 ms
6,504 KB
testcase_09 AC 564 ms
6,512 KB
testcase_10 AC 279 ms
6,480 KB
testcase_11 TLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"fmt"
	"bufio"
	"os"
)

var memo map[int]map[int]int

func main() {
	r := bufio.NewReader(os.Stdin)
	w := bufio.NewWriter(os.Stdout)
    defer w.Flush()
	memo = make(map[int]map[int]int)
	var T int
	fmt.Fscan(r, &T)
	for i := 0; i < T; i++ {
		var x int
		fmt.Fscan(r, &x)
		f := prime_factor(x)
		n := 1
		for _, j := range f {
			n *= j + 1
		}
		j := 2
		for !multiple(n, f, prime_factor(j)) {
			j++
		}
		fmt.Fprintln(w, x * j)
	}
}

func prime_factor(n int) map[int]int {
	if value, ok := memo[n]; ok {
		return value
	}
	res := make(map[int]int)
	for i := 2; i*i <= n; i++ {
		for n % i == 0 {
			value, ok := res[i]
			if ok {
				res[i] = value + 1
			} else {
				res[i] = 1
			}
			n /= i
		}
	}
	if n != 1 {
		value, ok := res[n]
		if ok {
			res[n] = value + 1
		} else {
			res[n] = 1
		}	
	}
	return res
}

func multiple(n int, f0 map[int]int, f1 map[int]int) bool {
	y := n
	for k, v := range f1 {
		if z, ok := f0[k]; ok {
			y = y / (z + 1) * (z + v + 1)
		} else {
			y *= v + 1
		}
	}
	return n * 2 == y
}
0