結果

問題 No.1871 divisXor
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:11:34
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,499 bytes
コンパイル時間 193 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 82,688 KB
最終ジャッジ日時 2025-06-12 14:12:23
合計ジャッジ時間 4,093 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def sum_of_divisors(x):
    if x == 0:
        return 0
    total = 0
    for i in range(1, int(x**0.5) + 1):
        if x % i == 0:
            total += i
            if i != x // i:
                total += x // i
    return total

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

def find_a_for_f_N(N):
    if N == 1:
        return 1
    a = N - 1
    if is_prime(a):
        return a
    max_check = min(N, 10**6)
    for x in range(2, max_check + 1):
        if sum_of_divisors(x) == N:
            return x
    return None

def main():
    N = int(sys.stdin.readline().strip())
    if N == 0:
        print(-1)
        return
    
    # Check if single element is possible
    a = find_a_for_f_N(N)
    if a is not None and a < 2 * N:
        print(1)
        print(a)
        return
    
    # Try triplet approach
    K = N ^ 13  # Because 1 XOR 12 is 13
    # Check if K can be represented as sum of divisors of some X
    max_check = min(K, 10**6)
    found = None
    for x in range(1, max_check + 1):
        if sum_of_divisors(x) == K:
            found = x
            break
    if found is not None and found < 2 * N - 7:
        print(3)
        print(1, 6, found)
        return
    
    print(-1)

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