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

@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 то откуда?

Новые блоги и статьи Все статьи Все блоги /
Оказывается, Unreal Engine позволяет качество на порядки выше, чем было в Lineedge Etyuhibosecyu 05.07.2026 Жаль, конечно, что я не узнал об этом, пока Lineedge существовала, а то бы Noname2331 написал, что волки превращаются в пиксельную кашу, а я бы его попросил скачать какую-нибудь бриллиантовую или Pro. . .	Doom для терминала без стрельбы и монстров. 3D Raycasting на ascii. dcc0 05.07.2026 Попросил нейронную сеть deepai. org написать рейкастинг 3D с библиотекой ncurses для Linux. Чтобы можно было ходить на стрелочки. Чтобы стены были отрисованы символами. Справилась. Первый вариант. . .	Установка статуса документа по условию Maks 05.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .	Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .
В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .	интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .	Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .

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

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,320
	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,320
	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,320
	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