Ш
но не понятно как найти ответы без нахождения самого цикла
Size: a a a
2020 April 28
Ш
мб кто знает ?)
CD
вроде понятно что чтобы существовал ответ нужно чтобы в компоненте должно быть нечетный цикл
как откуда зачем
CD
а, понял, чтобы не было (-1)^n собственной
CD
но не понятно как найти ответы без нахождения самого цикла
короче. на физике учили методу "обозначай и властвуй"
обозначь в компоненте одну неизвестную за x
обозначь в компоненте одну неизвестную за x
f
Как вычислить функцию эйлера на отрезке [1, 1e8] за < 3с ?
K
Как вычислить функцию эйлера на отрезке [1, 1e8] за < 3с ?
ну так простые числа до 1e4
f
ну так простые числа до 1e4
А дальше?
K
ну по определению - раскладываем число на простые, потом формула
phi(П p_i^k_i) = П (p_i - 1)p_i^{k_i - 1}
phi(П p_i^k_i) = П (p_i - 1)p_i^{k_i - 1}
f
Все 1e8 чисел будешь раскладывать?
f
Переслано от Kotomord_λapki
ну по определению - раскладываем число на простые, потом формула
phi(П p_i^k_i) = П (p_i - 1)p_i^{k_i - 1}
phi(П p_i^k_i) = П (p_i - 1)p_i^{k_i - 1}
MB
Как вычислить функцию эйлера на отрезке [1, 1e8] за < 3с ?
Можно линейным решетом. Зная min_prime, там парочка несложных ДП возникает
f
Можно линейным решетом. Зная min_prime, там парочка несложных ДП возникает
У меня получается что то не с линейным решетом за 5,5 с. Я считаю минимальный простой делитель, после по определению phi(ab) = phi(a) * phi(b), делю составное число на максимальную степень простого (res), чтобы получить два взаимно простых числа и вычисляю как phi[i] = phi[i/res] * phi[res]
Как это можно развить?
Как это можно развить?
MB
У меня получается что то не с линейным решетом за 5,5 с. Я считаю минимальный простой делитель, после по определению phi(ab) = phi(a) * phi(b), делю составное число на максимальную степень простого (res), чтобы получить два взаимно простых числа и вычисляю как phi[i] = phi[i/res] * phi[res]
Как это можно развить?
Как это можно развить?
res за константу ищешь?
f
res за константу ищешь?
Нет. Делю пока делится. В худшем случае это двоичный логарифм. Можно бинпоиском, но думаю константа хуже будет, хоть и log log n
Но не пробовал
Но не пробовал
MV
У меня получается что то не с линейным решетом за 5,5 с. Я считаю минимальный простой делитель, после по определению phi(ab) = phi(a) * phi(b), делю составное число на максимальную степень простого (res), чтобы получить два взаимно простых числа и вычисляю как phi[i] = phi[i/res] * phi[res]
Как это можно развить?
Как это можно развить?
а заранее посчитать часть простых чисел нельзя?
MB
Нет. Делю пока делится. В худшем случае это двоичный логарифм. Можно бинпоиском, но думаю константа хуже будет, хоть и log log n
Но не пробовал
Но не пробовал
Думаю, быстрее ДПшкой считать
f
Думаю, быстрее ДПшкой считать
А как? У меня не получается.
MB
mp_pow[n] = mp[n]
prev := n / mp[n]
if mp[n] == mp[prev] {
mp_pow[n] *= mp_pow[prev]
}
prev := n / mp[n]
if mp[n] == mp[prev] {
mp_pow[n] *= mp_pow[prev]
}