結果

問題 No.1871 divisXor
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:44:03
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,723 bytes
コンパイル時間 256 ms
コンパイル使用メモリ 81,944 KB
実行使用メモリ 127,384 KB
最終ジャッジ日時 2025-04-16 16:45:25
合計ジャッジ時間 11,811 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 WA * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    w = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += w
        w = 6 - w
    return True

# Precompute sigma up to 1e6
max_x = 10**6
sigma = [0] * (max_x + 1)
for i in range(1, max_x + 1):
    for j in range(i, max_x + 1, i):
        sigma[j] += i

sigma_dict = {}
for x in range(1, max_x + 1):
    s = sigma[x]
    if s not in sigma_dict:
        sigma_dict[s] = x

def find_solution(N):
    if N == 0:
        return [-1]
    
    # Check single number
    if N >= 1:
        candidate = N - 1
        if candidate > 0 and is_prime(candidate):
            if candidate < 2 * N:
                return [candidate]
    if N in sigma_dict:
        x = sigma_dict[N]
        if x < 2 * N:
            return [x]
    
    # Check pair (1, x)
    K_pair = N ^ 1
    candidate = K_pair - 1
    if candidate > 0 and is_prime(candidate):
        x = candidate
        if 1 + x < 2 * N:
            return [1, x]
    if K_pair in sigma_dict:
        x = sigma_dict[K_pair]
        if 1 + x < 2 * N:
            return [1, x]
    
    # Check triplet (1, 6, x)
    K_triplet = N ^ (1 ^ 12)  # 1^12 is 13
    if K_triplet in sigma_dict:
        x = sigma_dict[K_triplet]
        total = 1 + 6 + x
        if total < 2 * N:
            return [1, 6, x]
    
    return [-1]

def main():
    N = int(sys.stdin.readline())
    solution = find_solution(N)
    if solution[0] == -1:
        print(-1)
    else:
        print(len(solution))
        print(' '.join(map(str, solution)))

if __name__ == "__main__":
    main()
0