Большие числа

@Aleksogo · Регистрация: 05.11.2020

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

Здравствуйте, я написал программу, но для больших чисел время выполнения больше, чем нужно. Можете, пожалуйста, помочь исправить программу, чтобы время её выполнения было меньше. Заранее спасибо.
Вот программа на Питоне:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
n=int(input())
a=0
d=[]
c=[0]
f=[]
o=0
for i in range(1,n+1):
    for x in range(-n,n+1):
        for y in range(-n,n+1):
            if x<=n:
                if y<=n:
                    if x**2 + y**2==i**2:
                        a+=1 
                        y+=1 
                    else:
                        y+=1 
                else:
                    x+=1 
            else:
                i+=1 
    for j in range(1):
        d.append(a)
    for h in range(1):
        c.append(a)
    f=[d-c for d,c in zip(d,c)]
    o=f.index(max(f))
print(o+1)

@Gdez · 13.11.2020, 21:36

Miryz, А еще у них есть такие же интересные задачи?

Добавлено через 17 секунд
Вопрос без приколов

Добавлено через 3 минуты
А по поводу этой с ответом 192 можно подколоть их - при условии, что все числа целые, они решили квадратуру круга и определили конечность числа "пи"

@eaa · 13.11.2020, 21:40

задача на обычную факторизацию числа. она вообще по другому решается.

@Miryz · 13.11.2020, 21:44

Gdez,

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

18785

почему не 27625?

Добавлено через 1 минуту
факторизация 5*5*5*13*17

Добавлено через 44 секунды
показатели 3, 1, 1

@Gdez · 13.11.2020, 21:47

Miryz, ответ тестировщик выдал или сам нашел?

@Miryz · 13.11.2020, 21:49

Там нет тестировщика, сам нашел

@Gdez · 13.11.2020, 21:52

Miryz, но коды проверять можешь?

Добавлено через 1 минуту
Miryz, попробуй

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
pifpr = [5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97]
n = int(input())
s = n
i, a = 0, 1
while n - 1 :
    if pifpr[i] <= n :
        a *= pifpr[i]
        n //= pifpr[i]
        i += 1
    else :
        i = 0
# a - искомый радиус
print(a)

@Miryz · 13.11.2020, 21:52

Если принять что для промежутка до 325, радиус с большим кол-вом точек на окружности 325. Как на этом же промежутке у числа 325 наибольшее кол-во способов составления из суммы квадратов

Добавлено через 22 секунды
Gdez, ты полностью уверен в своей правоте?

@Gdez · 13.11.2020, 21:55

Miryz, 325 вроде включительно

Добавлено через 39 секунд
Miryz,

Gdez, ты полностью уверен в своей правоте?

Там штрафы за попытки?

@Miryz · 13.11.2020, 21:57

Кол-во способов составления числа 27625 - 8, а числа 18785 - 6

Добавлено через 20 секунд
Gdez, хуже, там нет попыток

Добавлено через 1 минуту

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

Кол-во способов составления числа 27625 - 8, а числа 18785 - 6

имею смелость заявить, что у радиуса 27625 будет больше точек на окружности

@Gdez · 13.11.2020, 21:59

Miryz, хреново
Я переделал алгоритм - после превышения следующего числа из pifpr остатка от числа - возвращаемся к началу списка

Добавлено через 33 секунды
Miryz, крайний код выдает 27625

Добавлено через 35 секунд
И цикл все таки до n == 1

@Miryz · 13.11.2020, 21:59

Если все так, как я сказал, то мне осталось только сделать перебор показателей

@Gdez · 13.11.2020, 22:01

Miryz, по идее можно запустить код, который в лоб, на ночь. А утром сверить с моим...
По крайней мере будут числа с верными решениями

@Miryz · 13.11.2020, 22:02

Gdez, аххаха, можешь взять мой алгоритм, правда постить я его не буду, пусть сами разбираются

@Gdez · 13.11.2020, 22:03

Как еаа упомянул - здесь только факторизацией. Но не просто по простым числам, а только по тем, которые есть в пифагоровых тройках в качестве числа "с".
Что я и пытаюсь реализовать

@Miryz · 13.11.2020, 22:04

Gdez,

Не по теме:

если хочешь посмотреть мое решение напиши в лс

@Gdez · 13.11.2020, 22:08

Miryz, имеешь в виду разложение по "n" и "m" троек?

Добавлено через 2 минуты
Мне неизвестен более быстрый алгоритм нахождения примитивных троек.
Потом просто умножаем на натуральные числа каждую тройку, пока не превысит заданное число и при условии, что такой тройки не было.
Но для 10^8 все равно оч долго

@Miryz · 13.11.2020, 22:15

Gdez,

Не по теме:

чек лс

@eaa · 13.11.2020, 22:57

простые числа которые дают остаток 1 при делении на 4.
Киньте сюда пяток тестов, для проверки.

такие тесты?

5000 - 108 - 4930
50000 - 324 - 45305
500000 - 540 - 499525
5000000 - 972 - 4987970

1) это n
2) максимальное количество целых точек
3) максимальный радиус

@Miryz · 13.11.2020, 23:20

eaa, 1) 4225 2) 27625 3)160225 4)4005625

@eaa · 13.11.2020, 23:31

4225 то откуда?

Новые блоги и статьи Все статьи Все блоги /
Благородство как наказание Maks 24.04.2026 У хорошего человека отношения с женщинами всегда складываются трудно. А я человек хороший. Заявляю без тени смущения, потому что гордиться тут нечем. От хорошего человека ждут соответствующего. . .	Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .	Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .
Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .	Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,318
	13.11.2020, 21:36
	Miryz, А еще у них есть такие же интересные задачи? Добавлено через 17 секунд Вопрос без приколов Добавлено через 3 минуты А по поводу этой с ответом 192 можно подколоть их - при условии, что все числа целые, они решили квадратуру круга и определили конечность числа "пи" 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	13.11.2020, 21:40
	задача на обычную факторизацию числа. она вообще по другому решается. 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,318
	13.11.2020, 21:47
	Miryz, ответ тестировщик выдал или сам нашел? 0

@Miryz 291 / 131 / 58 Регистрация: 24.11.2019 Сообщений: 532
	13.11.2020, 21:49
	Там нет тестировщика, сам нашел 0

@Miryz 291 / 131 / 58 Регистрация: 24.11.2019 Сообщений: 532
	13.11.2020, 21:52
	Если принять что для промежутка до 325, радиус с большим кол-вом точек на окружности 325. Как на этом же промежутке у числа 325 наибольшее кол-во способов составления из суммы квадратов Добавлено через 22 секунды Gdez, ты полностью уверен в своей правоте? 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,318
	13.11.2020, 21:59
	Miryz, хреново Я переделал алгоритм - после превышения следующего числа из pifpr остатка от числа - возвращаемся к началу списка Добавлено через 33 секунды Miryz, крайний код выдает 27625 Добавлено через 35 секунд И цикл все таки до n == 1 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,318
	13.11.2020, 22:01
	Miryz, по идее можно запустить код, который в лоб, на ночь. А утром сверить с моим... По крайней мере будут числа с верными решениями 0

@Miryz 291 / 131 / 58 Регистрация: 24.11.2019 Сообщений: 532
	13.11.2020, 22:02
	Gdez, аххаха, можешь взять мой алгоритм, правда постить я его не буду, пусть сами разбираются 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,318
	13.11.2020, 22:03
	Как еаа упомянул - здесь только факторизацией. Но не просто по простым числам, а только по тем, которые есть в пифагоровых тройках в качестве числа "с". Что я и пытаюсь реализовать 0

@Miryz 291 / 131 / 58 Регистрация: 24.11.2019 Сообщений: 532
	13.11.2020, 22:04
	Gdez, Не по теме: если хочешь посмотреть мое решение напиши в лс 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,318
	13.11.2020, 22:08
	Miryz, имеешь в виду разложение по "n" и "m" троек? Добавлено через 2 минуты Мне неизвестен более быстрый алгоритм нахождения примитивных троек. Потом просто умножаем на натуральные числа каждую тройку, пока не превысит заданное число и при условии, что такой тройки не было. Но для 10^8 все равно оч долго 0

@Miryz 291 / 131 / 58 Регистрация: 24.11.2019 Сообщений: 532
	13.11.2020, 22:15
	Gdez, Не по теме: чек лс 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	13.11.2020, 22:57
	простые числа которые дают остаток 1 при делении на 4. Киньте сюда пяток тестов, для проверки. такие тесты? 5000 - 108 - 4930 50000 - 324 - 45305 500000 - 540 - 499525 5000000 - 972 - 4987970 1) это n 2) максимальное количество целых точек 3) максимальный радиус 0

@Miryz 291 / 131 / 58 Регистрация: 24.11.2019 Сообщений: 532
	13.11.2020, 23:20
	eaa, 1) 4225 2) 27625 3)160225 4)4005625 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	13.11.2020, 23:31
	4225 то откуда? 0