結果

問題 No.1611 Minimum Multiple with Double Divisors
コンテスト
ユーザー 小野寺健
提出日時 2021-12-18 09:44:21
言語 Go
(1.23.4)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 11 TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

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