Kaosar et XOR#12228

Kaosar et XOR (Corrigé)

Auteur du problème:	Al Kaosar Hussain
Préparé par:	Hasan Saleh (MathModel)
Édité par:	Hasan Saleh (MathModel)

Solution Vous pouvez écrire une force brute en $O (n^{2})$ \mathcal{O}(n^2) et observer ce qui suit :

Pour un certain entier $k$

{n = 2^{k} ⟹ 2^{k + 1} - 2 n \neq = 2^{k} ⟹ 2^{⌈ l o g_{2} (n)⌉} - 1

\displaystyle \begin{cases} n=2^k \implies 2^{k+1}-2 \\ n \neq 2^k \implies 2^{\lceil \log_2(n) \rceil}-1 \end{cases}

Preuve :

Point 1 :

Pour certains entiers $n \leq 2^{m}$ n \le 2^m, alors tous $1 \leq i, j \leq n$ 1 \le i,j \le n alors tous $popcnt (i \oplus j) < 2^{m}$ \text{popcnt}(i \oplus j) < 2^m

Point 2 :

Écrivez $x$ en binaire avec au plus $m$ bits. Laissez son bit le plus élevé être à la position $k < m$ k<m. Ensuite, choisissez $i = 2^{k}$ i=2^k, $j = i \oplus x$ j=i \oplus x, puisque $x < 2^{m}$ x<2^m, nous avons $j < 2^{m}$ j<2^m et parce que $n > 2^{m - 1}$ n>2^{m-1} donc $i \oplus j = x$ i \oplus j=x

Point 3 : Pour les puissances de 2, le même processus se produit avec l'exclusion du bit le plus élevé $(2^{m - 1})$ (2^{m-1}), et donc la réponse est $2 n - 2$ 2n-2 dans ce cas.


#if n=puissance de 2 alors réponse 2*n-2
#if n n'est pas une puissance de 2, 2^(ceil(log2(n))-1

MOD=10**9+7

p=[1]
cur=1
for i in range(1,62):
    cur*=2
    p.append(cur)
    
def solve():
    n=int(input())
    if(n==2):
        print(1)
        return
    if(n in p):
        print((2*n-2)%MOD)
    else:
        log=0
        while(n>0):
            n//=2
            log+=1
        print((pow(2,log,MOD)-1)%MOD)
for _ in range(int(input())):
    solve()

Python

Complexité $O (lo g (n))$ .