結果

問題 No.3102 floor sqrt xor
コンテスト
ユーザー LyricalMaestro
提出日時 2026-10-29 01:42:09
言語 PyPy3
(8.0.0 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 39 ms / 2,000 ms
+ 301µs
コード長 1,553 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 81 ms
コンパイル使用メモリ 64,600 KB
実行使用メモリ 58,540 KB
最終ジャッジ日時 2026-10-29 01:42:24
合計ジャッジ時間 3,588 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/3102

import math

def to_2(N):
    array = []
    while N > 0:
        array.append(N % 2)

        N //= 2
    array.reverse()
    return array

def to_2x(N, k):
    array = []
    for _ in range(k + 1):
        array.append(N % 2)

        N //= 2
    array.reverse()
    return array

def sqrt(n):
    low = 0
    high = 2 * int(math.sqrt(n))
    while high - low > 1:
        mid = (high + low) // 2
        if mid ** 2 <= n:
            low = mid
        else:
            high = mid
    if high ** 2 <= n:
        return high
    else:
        return low

def solve(N):
    array = to_2(N)
    n = len(array)
    if n >= 2:
        n2 = n // 2
        n_base = 0
        for i in range(n2):
            n_base += (1 << (n - 1 - i)) * array[i]
        low = sqrt(n_base)
        high = sqrt(n_base + (1 << (n - 1 - (n2 - 1))) - 1)
        for sqrt_k in range(low, high + 1):
            k = N ^ sqrt_k
            if sqrt(k) == sqrt_k:
                return k
        return -1
    else:
        if N == 1:
            return - 1
        else:
            # N == 0:
            return 0



def solve2(N):
    array = to_2(N)
    for bit in range(2 ** len(array)):
        bit1 = sqrt(bit)
        if bit1 ^ bit == N:
            return bit
    return -1




def main():
    T = int(input())
    answers = []
    for _ in range(T):
        N = int(input())
        ans = solve(N)
        answers.append(ans)

    for ans in answers:
        print(ans)



                


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