정수의 임의의 거듭제곱들의 합을 바라보는 놀라운 방법

15319번: 동혁이의 생일선물

 

정수 x의 거듭제곱 $x^{0}, x^{1}, x^{2}, ... $에 대하여 이들의 모든 부분집합 A1, A2, ...을 생각하자

 

각 부분집합의 원소들의 합을 M1, M2,...라고 할 때 이들을 오름차순으로 정렬하면 수열 a1, a2,...를 얻는다

 

이때 k번째 원소 ak에 대하여 n개의 x,k가 주어질때 각각 구한 모든 ak의 합을 10^9 + 7로 나눈 나머지를 구한다

 

---------------------------------------------------------------------------------------------------------------------------------------------------------------

 

2,3,4,..부터 하나하나 생각해보면 이게 가능한건가? 생각이 들정도로 굉장히 어려운데

 

정수 x의 거듭제곱들로 이루어진 부분집합은 예를 들면 $x^{0}, x^{2}, x^{3}$, $x^{1}, x^{2}$, $x^{5}, x^{0}$...

 

이런것들이 있다

 

이들의 합은?

 

$x^{3} + x^{2} + x^{0}$

 

$x^{2} + x^{1}$

 

$x^{5} + x^{0}$

 

이는 사실 잘 보면 이진법 1101, 100, 100000를 x진법으로 표시한것과 마찬가지다

 

그러므로 오름차순으로 정렬한 수열 a1,a2,...,ak,...는 사실..

 

1,2,3,...,을 이진법 1,10,11,100,...으로 표현하고 이들을 x진법으로 표현한 것이다.

 

그러므로 k번째 수 ak에 대하여 k를 이진법으로 표현하고 이를 x진법으로 구하면 빠르게 구할 수 있다

 

1 > $x^{0}$

 

10 > $x^{1}$

 

11 > $x^{1} + x^{0}$

 

100 > $x^{2}$

 

...

 

from sys import stdin

n = int(stdin.readline())

mod = 10**9+7

v = 0

for _ in range(n):
    
    x,k = map(int,stdin.readline().split())

    k = bin(k)[2:]
    
    j = 0

    for i in range(len(k)-1,-1,-1):
        
        if k[i] == '1':
            
            v += pow(x,j,mod)
            v %= mod
        
        j += 1

print(v)