input_numbers=list(map(int,input().split()))
sum_number=0

def my_gen(a):
    i=0
    while i <= a:
        yield i
        i += 1

for i in my_gen(input_numbers[0]):
    sum_number += i**input_numbers[1]

print(sum_number%1000000009)

Я пробовал не использовать генератор, но это было слишком медленно. поэтому я попробовал снова с генератором, и это тоже было медленно.

Как я могу сделать это быстрее?//

Больше информации: Мой скоринговый бот говорит Time out. и (1<=input_numbers[0]<=1,000,000,000) (1<=input_numbers[1]<=50)

& Numpy не может быть использован

elon jeong

Ответов: 3

Ответы (3)

Код медленный, потому что вы берете большие экспоненты больших чисел. Но для конечного результата не требуется полная сумма, только модуль. Поэтому вы можете применить базовую модульную арифметику, чтобы уменьшить количество чисел в вашем вычислении и получить тот же конечный ответ.

Это плохая часть проблемы: https://projecteuler.net/problem=429. Но хорошая часть заключается в том, чтобы решить ее самостоятельно.

Вы можете использовать формулу Фаулхабера, которая потребует только цикла над значением мощности (а не миллиарда чисел от 0 до N).

from fractions import Fraction
from functools import lru_cache
@lru_cache()
def bernoulli(n,result=True): # optimized version
    A = [Fraction(1,n+1)]
    for j,b in enumerate(bernoulli(n-1,False) if n else []):
        A.append((n-j)*(b-A[-1]))
    return A[-1] if result else A

@lru_cache()
def comb(n,r):
    return 1 if not r else comb(n,r-1)*(n-r+1)//r

def powerSum(N,P):
    result = sum(comb(P+1,j) * bernoulli(j) * N**(P+1-j) for j in range(P+1))
    return (result / (P+1)).numerator

вывод:

powerSum(100,3) # 25502500

sum(i**3 for i in range(100+1)) # 25502500 (proof)

powerSum(1000000000,50)%1000000009 
# 265558322 in 0.016 seconds on my laptop

sum(i**50 for i in range(1000000000+1))%1000000009 
# 265558322 (proof in 16.5 minutes)

2022 WebDevInsider