結果

問題 No.1664 Unstable f(n)
コンテスト
ユーザー ID 21712
提出日時 2026-05-10 19:06:20
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,119 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 14,549 ms
コンパイル使用メモリ 284,568 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-05-10 19:06:43
合計ジャッジ時間 13,296 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"
import . "math"

func xrt(a, x int) int {
	p := max(2, int(Ceil(Pow(float64(a),1/float64(x)))))
	for {
		pp := a
		for i := 0; i < x; i++ {
			pp /= p
		}
		if pp > p {
			p++
		} else {
			break
		}
	}
	for {
		pp := a
		for i := 0; i < x; i++ {
			pp /= p
		}
		if pp == 0 {
			p--
		} else {
			break
		}
	}
	return p
}


func main() {
	var n int
	Scan(&n)
	if n <= 3 {
		// i = 1, j = 0, k = n-1
		// n = 1^0 + (n-1)
		Println(n)
		return
	}
	ans := n+1
	for j := 2; j <= 63; j++ {
		i := xrt(n, j)
		ij := 1
		for a := 0; a < j; a++ {
			ij *= i
		}
		k := n-ij
		ans = min(ans, i+j+k)
		println("i=",i,",j=",j,",k=",k,",ij=",ij)
	}
	Println(ans)
}

/*
考察

n = i^j + k
 
iを固定したとき
i^jのときの k と
i^(j-1)のときの k' を
比較すると
k = n - i^j
k' = n - i^(j-1)

k' - k = n - i^(j-1) - (n - i^j)
       = i^j - i^(j-1)
       = i^(j-1) * (i-1)
k' = k + i^(j-1) * (i-1)
これはかなり大きな値なので
iを固定したとき j は最大限に大きく取る必要がある
i^(j+1) では n を超えてしまう
つまり
i^(j+1) > n = i^j + k
i^(j+1) - i^j > k
i^j * (i-1) > k
が k の上界？
最小の k とは k=0 で n = i^j のとき
よって k の取りうる範囲は
0 <= k < i^j * (i-1)

j は n の最大が 10^18 なので整数型の2の補数表現的に j < 64 ではあるはず

jを固定することを考える
j = 0 のとき i=1 k=n が最適？
n = 1^0 + n  -> ans = 1 + 0 + n
j = 1 のとき i=n k=0 が最適？
n = n^1 + 0  -> ans = n + 1 + 0

j = 2 のとき i は
pow(n,1/3) < i <= pow(n,1/2)
の範囲
i^2 のときの k と
(i-1)^2 のとき k' と比較すると
k = n - i^2
k' = n - (i-1)^2

k' - k = n - (i-1)^2 - (n - i^2)
       = i^2 - (i-1)^2
       = (i + (i-1)) * (i - (i-1))
       = 2*i - 1
つまり j を固定したとき i は最大限に大きく取ったほうがよい？

コーナーケース？

n = 1 のとき
i = 1, j = 0, k = 0 の ans = 1 が最適ぽい

n = 2 のとき
i = 1, j = 0, k = 1 の ans = 2 が最適ぽい

n = 3 のとき
i = 1, j = 0, k = 2 の ans = 3 が最適ぽい


*/
0