結果

問題 No.1198 お菓子配り-1
コンテスト
ユーザー ID 21712
提出日時 2026-06-04 18:08:16
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 1,866 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 11,542 ms
コンパイル使用メモリ 278,280 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-06-04 18:08:35
合計ジャッジ時間 12,418 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

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

func main() {
	var n Int
	Scan(&n)
	if n.Cmp(NewInt(2)) <= 0 {
		Println(-1)
		return
	}
	if n.Bit(0) != 0 {
		Println(1)
		return
	}
	if n.Bit(1) != 0 {
		Println(-1)
		return
	}
	if n.Cmp(NewInt(8)) >= 0 {
		Println(1)
	} else {
		Println(-1)
	}
}

/*
考察

10^25はint64には収まらんらしい…

A^2 - B^2 = N
因数分解すると
(A + B) * (A - B) = N
これからわかることは…ない
Nが素数の場合に限り
A - B = 1
A + B = N
に一致するものがあればokか？(N=2はダメだな…)
これ、Nが3以上の奇数なら任意に可能か
A=ceil(N/2),B=floor(N/2)
とすれば成立かな…？

Nが偶数とすると
AとBの偶奇は一致する必要がある
A ≡ B (mod 2)
AとBの偶奇が一致すると
A+BもA-Bも偶数になるので
A + B ≡ A - B ≡ 0 (mod 2)
Nは4の倍数である必要がある
AとBは偶数と仮定して
A = 2 * X
B = 2 * Y
N = 4 * Z
と置くと
(A + B) * (A - B) = N
4 * (X + Y) * (X - Y) = 4 * Z
(X + Y) * (X - Y) = Z
と変換できる…
つまり、再帰…
しかし、これだとサンプル2のN=8がACできない(Z=2で-1)
つまり、AとBが奇数の場合でも考える必要がある
A = 2 * U + 1
B = 2 * V + 1
N = 4 * W
(A + B) * (A - B) = N
4 * (U + V + 1) * (U - V) = 4 * W
(U + V + 1) * (U - V) = W
と変換できる
U - V = 1 と仮置きすると
U + V + 1 = (V + 1) + V + 1 = 2 * (V + 1) = W
これはWが4以上の偶数なら成立する(つまりNは16の倍数…)
やはりこれでもサンプル2のN=8はACできない…
サンプル2の説明書きを参考にすると
A - B = 2 となる
つまり
(A + B) * (A - B) = ((B + 2) + B) * 2 = 4 * (B + 1) = N
これはつまりNが8以上の4の倍数なら成立することを意味する

なお、N=4は暗算でも成立しないことがわかる

*/
0