탐색 범위를 줄여야하는 브루트포스 연습1 - 각 자릿수의 제곱합?

17755번: Równanie

 

정수 k가 주어질때 a <= n <= b인 정수 n에 대하여 kf(n) = n을 만족하는 n의 개수를 구해야한다.

 

여기서 f(n)은 n을 10진법으로 표현했을 때 각 자릿수의 제곱합

 

k,a,b <= 10^18이라 a <= n <= b인 모든 n에 대해 해볼수는 없다

 

이럴때는 탐색범위를 좁힐 수 있는지 생각해봐야한다

 

 

f(n)이 n을 10진법으로 표현했을 때 각 자릿수의 제곱합이므로, 

 

$n = a_{1} * 10^{x_{1}} + a_{2} * 10^{x_{2}} + a_{3} * 10^{x_{3}} + ... $이므로 

 

$f(n) = a_{1}^{2} + a_{2}^{2} + .... $인데 여기서 $a_{i} <= 9$이다.

 

그런데 n이 최대 10^18이므로 f(n)이 최대가 될려면 999999999999999999로 9가 18개 있는경우이다.

 

이 경우 81*18 = 1458이라서 f(n)으로 가능한 값은 1부터 1458까지이다.

 

 

그러므로 f(n)을 기준으로 1부터 1458까지 모든 경우에 대해 kf(n)을 구할 수 있고 a <= kf(n) <= b를 만족하는지 검사하고

 

kf(n) = n으로 구한 n의 f(n)값이 실제로 맞는지도 검사해야한다

 

def f(n):
    
    value = 0

    for i in range(len(n)):
        
        value += (int(n[i])*int(n[i]))
    
    return value

k,a,b = map(int,input().split())

count = 0

for x in range(1,1459):
    
    n = k*x

    if n >= a and n <= b:

        v = f(str(n))

        if v == x:
            
            count += 1

print(count)