flaass: S pylu, s zharu

(Добавить комментарий)

	mike67@lj 2008-07-17 08:17 (ссылка)
	Странный вопрос. Вы же сами пишете, что будете проверять решение. Значит, этот простой делитель есть. (Ответить) (Ветвь дискуссии)

	flaass@lj 2008-07-17 08:25 (ссылка)
	Proverju, pravda li pjatero :) (Ответить) (Уровень выше) (Ветвь дискуссии)

	mike67@lj 2008-07-17 08:58 (ссылка)
	Само собой. Но если б этого делителя не существовало, Вы бы и не стали проверять! (Ответить) (Уровень выше)

	rus4@lj 2008-07-17 15:12 (ссылка)
	Какв вообще дела? http://www.pdmi.ras.ru/~olymp/2001/problems.html отбор 11 класса, третья задача (Ответить) (Ветвь дискуссии)

	xoled@lj 2008-07-17 16:54 (ссылка)
	А чем она вот так вот уж похожа на эту? Идеей брать в качестве n числа до (p-1)/2? (Ответить) (Уровень выше) (Ветвь дискуссии)

rus4@lj
2008-07-17 17:14 (ссылка)

В каком смысле "идеей"? Это все решение. Ну, надо еще доказать, что если n^2+1 кратно p и p>2n, то p>2n+sqrt(2n), это совершенно стандартное упражнение (обозначим p=2n+k, тогда k^2+4 делится на p, что и влечет требуемую оценку).

(Ответить) (Уровень выше) (Ветвь дискуссии)

xoled@lj
2008-07-17 17:32 (ссылка)

Да я понимаю, что задачи как таковой нет, но "идея" тоже не то чтобы очень нетривиальна. То есть задача скорее просто плоха, чем вторична. Раз уж поставили, могли бы хоть наворот какой-нибудь еще сделать -- типа 2n+\sqrt{4n}, а так даже по сложности не тянет.

(Ответить) (Уровень выше) (Ветвь дискуссии)

rus4@lj
2008-07-17 17:52 (ссылка)

Я много давал эту задачу разным детям, решали всегда плохо. Так что идея видимо нетривиальна (искать n по p, а не наоборот). То, что ты пишешь --- это что ли о том, что не вес простые вида 4k+1 имеют вид a^2+4? Да уж наверно не все. По-моему так не стоит городить технические сложности ради грошового улучшения оценки. На МЛ есть пост, где доказывают оценку C*n для любого C --- это в самом деле интересно.

(Ответить) (Уровень выше) (Ветвь дискуссии)

xoled@lj
2008-07-17 18:33 (ссылка)

Я и написал, что наворот, бессмысленно, да. Прочитал на мл, неплохо.
Может, идея и нетривиальна, но номер 3 на имо таким быть не должен все равно. У тебя просто задача в оперативной памяти, я ничего крамольного в совпадении не вижу. Если бы она еще на своей позиции стояла.
Вообще вариант близок к отвратительному, по-моему. Шестая вот разве что хорошая.

(Ответить) (Уровень выше)

	flaass@lj 2008-07-17 17:30 (ссылка)
	Dela tak sebe. Nadeemsa na 6 zolotyx i na vtoroe mesto v celom. No i tam, i tam uverennosti net. (Ответить) (Уровень выше) (Ветвь дискуссии)

	rus4@lj 2008-07-17 17:55 (ссылка)
	Удачи! (Ответить) (Уровень выше) (Ветвь дискуссии)

	flaass@lj 2008-07-17 18:51 (ссылка)
	A mozhno ssylku na ML pro C*n? Net vremeni iskat' samomu. (Ответить) (Уровень выше) (Ветвь дискуссии)

	xoled@lj 2008-07-17 19:05 (ссылка)
	http://www.mathlinks.ro/viewtopic.php?search_id=550514793&t=126781 А сколько наших шестую сделало? (Ответить) (Уровень выше) (Ветвь дискуссии)

	flaass@lj 2008-07-17 19:33 (ссылка)
	Spasibo! Po predvaritel'noj ocenke, shestuju sdelalo 0. Prichem ona predlozhena nami :) (Ответить) (Уровень выше)

	rus4@lj 2008-07-18 01:28 (ссылка)
	http://www.mathlinks.ro/viewtopic.php?search_id=550514793&t=126781 (Ответить) (Уровень выше)

	rus4@lj 2008-07-20 12:53 (ссылка)
	халявщики молодцы! (Ответить) (Уровень выше) (Ветвь дискуссии)

	flaass@lj 2008-07-20 21:31 (ссылка)
	Sami obaldeli :) (Ответить) (Уровень выше)