結果

問題 No.2480 Sequence Sum
ユーザー ID 21712
提出日時 2025-05-03 22:22:56
言語 Go
(1.23.4)
結果
AC  
実行時間 2 ms / 500 ms
コード長 1,816 bytes
コンパイル時間 14,325 ms
コンパイル使用メモリ 256,728 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-05-03 22:23:11
合計ジャッジ時間 12,799 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import . "fmt"

func main() {
	var n int
	Scan(&n)
	Println(solve(n))
}

func solve(n int) int {
	// 隣り合う整数 X X+1
	// XがC個、X+1がD個 (C >= 1 && D >= 1)
	// LEN = C + D (LEN > D && LEN > C)
	// N = X*C+(X+1)*D = X*(C+D) + D = X*LEN + D
	// うーん、N-D=X*LEN
	// (N - D) / X = LEN
	// N = X*LEN1 + D1
	// LEN2 = LEN1 - 1
	// N = X*LEN2 + D2
	// N = X*(LEN1-1) + (D1+X)
	// N = X*(LEN - Ki) + (D + Ki * X)
	// LEN - Ki > D + Ki * X
	// LEN > D + Ki * (X + 1)
	// N % X == 0 のとき LEN = N / X のみ
	// N % X != 0 のとき (LEN - Ki) = (N - (D + Ki * X)) / X
	//                   LEN = (N - D) / X - Ki * (X + 1)
	//                   N = X * LEN + D + Ki * X * (X + 1)
	//                   LEN - Ki つまり任意サイズとれる？
	//                   (N - D) / X > Ki * (X + 1)
	//                   (N - D) / X / (X + 1) > Ki
	//                   LEN / (X + 1) > Ki
	// D = N % X ？これはDの最小？
	// 0 <= D < X ？
	// X + (X + 1) <= N より X <= (N - 1) / 2
	// さすがに全探索は無理そう(N=1e9のときなど)
	// ------------------
	// LEN=2 のとき [X, X+1]
	// LEN=3 のとき [X, X, X+1] ... [X, X+1, X+1]  (sumdiff 0 ... 1) (sum 3X+1 ... 3X+2)
	// LEN=4 のとき [X,X,X,X+1] ... [X,X+1,X+1,X+1] (sumdiff 0 ... 2) (sum 4X+1 ... 4X+3)
	// LEN=5 のとき [X,X,X,X,X+1] ... [X,X+1,X+1,X+1,X+1] (sumdiff 0 ... 3) (sum 5X+1 ... 5X+4)
	// LEN=6 のとき [X,..,X,X+1] ... [X,X+1,...,X+1] (sumdiff 0 ... 4) (sum 6X+1 ... 6X+5)
	// 長さに対してXは一意に決まるぽい？
	// さらに言うなら、Nの約数のLENにはならないぽい？
	// つまり、Nと互いに素なN未満の数の総数？
	m := map[int]bool{}
	for x := 1; x * x <= n; x++ {
		if n % x == 0 {
			m[x] = true
			m[n/x] = true
		}
	}
	return n-len(m)
}
0