mingssssss

1.質問

0と1からなる無限の長さの文字列Xがある.この文字列は、次のプロシージャによって作成されます.
Xは最初は「0」で始まる.
Xから0から1、1から0までの文字列Xを作成します.
XにXを付けた文字列をXとして再定義します.
2～3のプロセスを無限に繰り返します.
すなわち、Xは最初は「0」で始まり、「01」になり、「0110」になり、「011010101」になる.

    "011010011001011010010110011010011001011001101001⋯⋯"

自然数kが与えられたとき,Xのk番目のk文字は何であるかを求める.
入力
第1行は自然数k(1≦k≦10^18)を与える.
しゅつりょく
最初の行にk番目の文字を出力します.
入力例1
1
サンプル出力1
0
入力例2
2
サンプル出力2
1
入力例3
10
サンプル出力3
0

2.コード

k = int(input()) # 입력값
n  = 0 # 2^n을 구할 변수
cnt = 0 # 연산이 몇 번 이루어 졌는지 확인하는 변수

while k > 2: # 0과 1만 구하면 되므로,
    if k > 2**n:
        n += 1
    else:
        n -= 1 # n값 그대로 사용하면 음수가 나온다.
        k = k - (2**n)
        n = 0
        cnt += 1
if k == 1:
    if cnt % 2 == 0:
        print('0')
    else:
        print('1')
elif k == 2 or k == 0:
    if cnt % 2 == 0:
        print('1')
    else:
        print('0')

3.コメント

初めて見た時は問題に沿ってコードを作ると解りやすいと思ったけど….10^18に入力すると、大きな数字が入ってきて、whileドアもforドアも大きな数字が入ってきて、もちろんメモリオーバーフローが発生します.
直接数字を接続する方法では処理できないようなので、kを減らす方法を考えました.
自分で20の数字を書きましたが、kから2^nを繰り返すと、最終的には1番目か2番目の数字にまとめられることに気づきました.このロジックを用いて,1番目の数字か2番目の数字かを確認した後,kから2^n引いたcntを分けて数え,cntが偶数であれば元の数字なので,数字の大きさによって奇数であれば逆の数字を出力する.この問題を解決するためには,入力値と演算を効果的に減らす方法をよく考慮しなければならない.
他の接着剤を見て、点火式を使いました.点火式は不慣れですが、慣れるように頑張ります.

k = int(input())
def recursive(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n%2:
        return 1-recursive(n//2)
    else:
        return recursive(n//2)
print(recursive(k-1))

*参照(1行モンスターコード)

print(bin(int(input())-1).count('1')%2)