Задача по олимпиадному программированию не проходит по времени

@supermegahaxer · Регистрация: 29.03.2020

Студворк — интернет-сервис помощи студентам

Problem C. What a sequence!
Input file: standard input
Output file: standard output
Time limit: 2 seconds
Memory limit: 512 mebibytes
Let an be a sequence defined by the recursive formula:
an+2 = k · an+1 + an
a0 = 0
a1 = 1
Given a certain k ∈ {1, 3, 5, 7} and an odd prime number p, your task is to find the value of ap mod p.
Input
In the first line one integer Z ≤ 106
is given, denoting number of testcases described in following lines.
For each test case, first and the only input line contains two natural numbers p and k, p being an odd
prime number.
k ∈ {1, 3, 5, 7}. The total length of the numbers p in the all testcases doesn’t exceed 106
.
Output
For each test case you should print exactly one line containing the value of ap mod p.

------------------------------------------------------------------------------------------------------------------------------
мой код не проходит по времени, не понимаю, что с этим делать, голова подсказывает, что без c++ не стоит даже соваться в олимпиадки, это так? ну и с кодом посмотрите, что не так, вроде все выводит верно...

Python
1
2
3
4
5
6
7
8
9
10
11
a_0 = 0
a_1 = 1
for i in range(int(input())):
    p, k = map(int, input().split())
    for j in range(p - 1):
        a_new = k * a_1 + a_0
        a_0 = a_1
        a_1 = a_new
    print(a_new % p)
    a_0 = 0
    a_1 = 1

@eaa · 29.03.2020, 14:04

а какая разница какой язык? если алгоритм не правильный.
что вам с++ дай что питон, это ничего не изменит.

@supermegahaxer · 29.03.2020, 15:36 **[ТС]**

в этом и проблема, что алгоритм вроде правильный, но времени тратит больше, чем надо...

@Garry Galler · 29.03.2020, 16:13

Сообщение от supermegahaxer

голова подсказывает, что без c++ не стоит даже соваться в олимпиадки, это так?

Нет. Туда не стоит соваться без наличия интеллекта и знаний.
Ваш код алгоритмически неоптимален, именно поэтому он очень долго работает.
А уповать на С++ ... боже какая детская наивность...

@eaa · 29.03.2020, 16:23

supermegahaxer, зачем вам памяти 512 Мб дают?

Новые блоги и статьи Все статьи Все блоги /
Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .
Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	29.03.2020, 14:04
	а какая разница какой язык? если алгоритм не правильный. что вам с++ дай что питон, это ничего не изменит. 0

@supermegahaxer 0 / 0 / 0 Регистрация: 29.03.2020 Сообщений: 5
	29.03.2020, 15:36 [ТС]
	в этом и проблема, что алгоритм вроде правильный, но времени тратит больше, чем надо... 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	29.03.2020, 16:23
	supermegahaxer, зачем вам памяти 512 Мб дают? 0

Задача по олимпиадному программированию не проходит по времени

Решение