Есть два целых числа, которые уменьшаются на единицу одновременно, пока одно из них не станет равным нулю, нужно посчитать сколько раз будет такое, что одно из чисел будет делиться нацело на другое число.
Время выполнения сильно важно, ибо при любых входных данных программа должна выполняться менее, чем за 1 секунду.
Числа могут быть 1 <= x <= 10^9
Да нормально я постчу
Начни с онлайн-курсов арифметики, они бесплатны, если оч понравится — задонатишь им сто рублей
Спасибо за наводку
Че ты бампаешь, дегенерат? Тебе же уже написали выше, что для начала нужно хотя бы арифметику выучить.
ну раз такой умный, то подскажи, чего уж
В один цикл (до меньшего числа) - слишком медленно
Важно же не кол-во циклов, а сложность алгоритма.
от
быстрофикс
Я ошибся, тебе не начала школьной программы нужны, а лоботомия. Тебе это никак уже не поможет, но хотя бы буянить и срать говнотредами перестанешь.
Ну и в чем проблема? В первой итерации цикла проверяешь, какое число больше, его потом целочисленно делишь на другое, если получается 0, то счётчик +1. Если оба числа равны, то счётчик можно сразу ставить равным им, ибо число на само себя всегда нацело делится.
> должна выполняться менее чем за 1 секунду
> 10^9
Если оба числа будут хотя бы близки к этому самому миллиарду, то за секунду это тебе даже суперкудахтер не посчитает
А как ты меньше чем за 1 цикл будешь уменьшать числа по единице?
Как я уже писал выше - так слишком медленно
Должно быть решение явно меньше чем O(n)
Мне интересно нахуй вы пишите это? Ты ж блять вряд ли студент даже, ты вообще в теме не шаришь. Но зачем-то приходишь в унылый тред с лабами и строчишь этот бесполезный пост. Зачем?
Что должно мне похую. У тебя скажем есть n=10
как ты меньше чем за 10 итераций получишь из него 0? Только если сразу сделаешь 10 - 10, но в условии сказано, что именно по единице отнимается
разумист в треде
Ну без цикла тут никак не обойдёшься. Можно попробовать параллельное погромирование, если у тебя цопэ многоядерный что в 2к20 наверняка так. Гугли OpenMP или MPI, но это на крестах, на питоне хз есть ли аналоги. И опять же сомневаюсь что даже так удастся уложиться в секунду, ибо диапазон значений слишком большой. Вот если бы хотя бы одно из чисел было бы хотя бы до 100 миллионов, то думаю за секунду затащилось
Еще один гений алгоритмической мысли.
В цикле могут быть условия, за счет которых ты будешь пропускать итерации например
О, вижу эксперта в треде. Вы такой молодец. Из тысячи двести будете тоже в цикле вычитать из восьмиста итераций?
Пиздец ты еблан, ты ж просто нулевой.
А по теме, нахуй писать на мпи в питоне в циклической задаче? Ну хотя че я хочу, ты ж в теме не разбираешься.
>>230746318
>которые уменьшаются на единицу одновременно, пока одно из них не станет равным нулю
которые уменьшаются на единицу одновременно
НА ЕДИНИЦУ
Если ты пропустишь итерацию, то по итогу у тебя число будет 1, пропустишь две итерации, будет 2 и т.д.
Ну смотри
Есть x,y
Есть переменная N, считающая РАЗЫ
Есть цикл, уменьшающий x,y на 1
Тебе нужно:
До цикла определить, что на что делить. Можно задать новые переменные, например - "If x>y: x,y = max,min Else: x,y = min,max"
Дальше при каждой итерации производить операцию "If max%min ==0: N+=1"
Ну и не забыть про ситуацию, когда x=y.
Мимо давно не прогер.
const calculate = (a, b) => {
let newA = a;
let newB = b;
let result = 0;
while (true) {
if (newA === 0 || newB === 0) {
return result;
}
if (a % b === 0 || b % a === 0) {
result++;
}
newA--;
newB--;
}
};
ГЕНИЙ.
А вычитать сразу 2 перед пропуском никак нельзя?
Тогда одновременно числа уменьшатся на ДВА, сука тупой ты даун
> нахуй писать на мпи
> в циклической задаче
А, так это троллеркоастер а не тред, как же я сразу не догадался. Сажаскрыл, тебе рака очка
Ага. А еще небо голубое большую часть времени.
Че сказать то хотел?
>>230746486
Писал выше, что так слишком медленно выходит
За О(n) отрабатывает же.
>Мимо давно не прогер.
Ну мы видим. А в унылый тред со своим дебильным решением прибежал. Тут же за 30 постов до тебя никто не догадался до такого, слава богу ты пришел, рачина.
Я не оп и я пишу с сажей.
И свои вопросы я задал абсолютно серьезно, ты глупость какую-то высрал.
Прочитай внимательно еще раз ОП-хуй-пост.
Там ничего не сказано о том, что только в каждой ИТЕРАЦИИ должна вычитаться единица.
Там сказано только то, что они уменьшаются одновременно
Ты оп?
Даю наводку: разность этих 2 чисел - константа. А дальше стоит поработать мозгом, а если не выходит, то идти учить арифметику основы теории чисел и делимости
Да, пожалуй, дальше будут ставить метку
Я ему уже советовал выше, этот еблан не хочет ничего слушать.
Понятно, задача чисто математическая к погромированию не относится
Да, про итерации ничего. Но указано, что уменьшаются только на ЕДИНИЦУ одновременно. Неужели это настолько неочевидно, я хуею
Ты себя не успокаивай, задача на примитивнейшую матешу, я, например, в работе использую вышмат куда серьезнее, так что пока не выучишь нормально математику, на работу тебя не возьмут.
Если для тебя задача уровня 2+2*2 слишком математическая и к погромированию не относится, то ты не относишься к человеку разумному
Либо работай с разностью двух чисел (константа же), либо с квадратным корнем большего числа. И так и так должно получиться быстро.
Я уже за 200к работаю фронтендером нахуй ненужна твоя матеша.
Джейсоны надо в дивы оборачивать
Ты троль, никто не знает такую математику, даже загуглить не смог причем тут разность константа и какое это ваще отношение имеет к делимости чисел друг на друга.
Ага, охотно верю.
>Ты троль, никто не знает такую математику, даже загуглить не смог причем тут разность константа и какое это ваще отношение имеет к делимости чисел друг на друга.
> на примитивнейшую матешу
Именно поэтому ты только визжишь с сагой и брызжишь ядом на весь тред, вместо того чтобы рассказать, как же эта примитивнейшая задача решается?
>два целых числа
Примем наименьшее как a, большее - как b. d = b-a.
Тогда имеем два ряда A = (0..a) и B = A+d.
Тогда очевидно, что чтобы член из ряда A был частным от соотв. ряда B - член из B должен быть больше или равен чем соотв. член А. Поэтому если ты и собрался проверять циклом то проверять имеет смысл только в A=(0..MIN(a,d)). Когда текущее число из ряда A > d то условие целочисленного деления (Ax+d)/Ax никогда не будет выполняться.
Пруф за щекой поищи................
>и собрался проверять циклом то проверять имеет смысл только в A=(0..MIN(a,d)).
А теперь давай подумаем, пройдя по этому циклу и уменьшая числа по единице, одно из них станет нулём?))))))))))
Жирная зелень забайтила на срач, а тупые постаноны его кормят весь тред. Картина маслом
>пройдя по этому циклу и уменьшая числа по единице, одно из них станет нулём?))))))))))
Скобкодаун, хули ты там уменьшать собрался свои циклом, ммм?
Я тебе расписал два связанных числовых ряда а ты дауненок все никак уменьшать по единице не перестанешь.
Можно линк на таск?
Линка не имеется, ибо задачку выдали в устном виде
Пруф ми вронг
Братан, не так все просто, офер горит, роадмап мутный, коуч сказал что на мое место много реплаев, поэтому показать не могу
Потому что если этого не делать, то очевидно число не будет нулём и это уже совсем другая история, не касающаяся задачи итт.
ЕСЛИ надо уменьшать числа по единице одновременно, пока одно из них не станет нулём, то решение только одно и оно O(n)
ЕСЛИ это не нужно делать, тогда O(1).
Надо срочно проводить тимбилдинг ИТТ. А то что-то коворкинг не задался
Вот давай О(1)
>очевидно число не будет нулём
Какое, блядь, число не будет нулем? Ты сейчас придрался что в условии числа >=1 а у меня ряды с нуля начинаются? Ну хуй с тобой, пусть с 1 начинаются, это ничего не меняет.
За O(sqrt(n)) у меня получилось с небольшими багами.
Прямо сейчас созвонился с коучем, он дал выход на мамку ОПа. Сейчас еду на тимбилдинг с ней в антикафе. Посоветуйте годный саундтрек под этот кейс
>с небольшими багами
Так это и не решение вовсе тогда.
Ты долбоеб. У тебя задача найти количество таких пар, хуйня про итерации дана для наглядности потому что про ряды ты нихуя не знаешь. Итерации твои мудацкие не касаются решения, максимум пользы от них это промоделировать на листочке и найти закономерности, зависящие от разности чисел как тебе уже написали
Это решение, которое проходит не все группы тестов.
Элджей + морген, треки по вкусу выбирай. Эти сонгеры всегда настраивают меня на тимбилдинг
Сейчас я буду считать сколько фаллических предметов проходят в твою жопу, судя по тому что у меня есть, не все из них пройдут
Если числа слишком большие, скажем, больше ляма каждое, то перед циклом делишь их на 1000, только потом считаешь счётчиком. В конце счётчик умираешь на тысячу, вот тебе и ответ.
/thread
вот уже условие меняется, так пиндосы и проталкивают хуйню про большие взрывы и т.д
Ну гений, сразу видно
ебать даун
> Ну гений, сразу видно
>>230748689
> ебать даун
>Если числа слишком большие, скажем, больше ляма каждое, то перед циклом делишь их на 1000, только потом считаешь счётчиком. В конце счётчик умираешь на тысячу, вот тебе и ответ.
>/thread
Да, именно поэтому.
Ты, видимо, в силу своей тупости, не понимаешь чего я хочу и мои мотивы.
Я хочу: интересные треды с умными людьми
Я не хочу: неинтересные треды с лабами, которые создал идиот
Поэтому я всячески саботирую все, что мне нравится.
слушаем гимн хохлов
>>230747217
Да, именно поэтому пидораха крым
Ты, видимо, в силу своей тупости пыня хуйло, не понимаешь чего я хочу и мои Крым Навальный мотивы.
Я хочу: интересные Крым Навальный Донбасс пидорашки треды с умными людьми
Я не хочу: Пыня хуйло +15 неинтересные треды с лабами, которые создал идиот
Поэтому я всячески саботирую все, что мне нравится.
>ни одного решения на ideone
Это правда
> Не отравлен
Держи, няш
Сап, б. Решаю задачки по Пыня Донбасс хохлы и вот что-то не могу допереть:
Есть два Навальный числа, которые уменьшаются на единицу одновременно Крым, пока одно из них не станет равным нулю Донбасс, нужно посчитать сколько раз будет такое, что одно из чисел будет делиться нацело на другое число.
Время выполнения сильно пидораха, ибо при любых входных данных долбильня лахты должна выполняться менее, чем за 1 секунду.
Числа могут быть +15
Писал же, что O(n) не прокатит, нужно меньше
> while n1 > 0 and n2 > 0:
измени на это, я неправильно условие прочёл
while n1 > 0 or n2 > 0:
> Это же даунская задача
> ОП с тебя пиздатая webm за то что я потратил 30 секунд своего времени.
Опять ОП-метка отклеилась
> Сап, б. Решаю задачки по Пыня Донбасс хохлы и вот что-то не могу допереть:
> Есть два Навальный числа, которые уменьшаются на единицу одновременно Крым, пока одно из них не станет равным нулю Донбасс, нужно посчитать сколько раз будет такое, что одно из чисел будет делиться нацело на другое число.
> Время выполнения сильно пидораха, ибо при любых входных данных долбильня лахты должна выполняться менее, чем за 1 секунду.
> Числа могут быть +15
>O(n)
в душе не ебу что это, давай по русски
> > while n1 > 0 and n2 > 0:
> измени на это, я неправильно условие прочёл
> while n1 > 0 or n2 > 0:
> Да, именно поэтому пидораха крым
> Ты, видимо, в силу своей тупости пыня хуйло, не понимаешь чего я хочу и мои Крым Навальный мотивы.
> Я хочу: интересные Крым Навальный Донбасс пидорашки треды с умными людьми
> Я не хочу: Пыня хуйло +15 неинтересные треды с лабами, которые создал идиот
> Поэтому я всячески саботирую все, что мне нравится.
> Давайте проясним раз и навсегда.
> ЕСЛИ надо уменьшать числа по единице одновременно, пока одно из них не станет нулём, то решение только одно и оно O(n)
> ЕСЛИ это не нужно делать, тогда O(1).
Временная сложность будет линейно возрастать в зависимости от входных данных
> Ну смотри
> Есть x,y
> Есть переменная N, считающая РАЗЫ
> Есть цикл, уменьшающий x,y на 1
> Тебе нужно:
> До цикла определить, что на что делить. Можно задать новые переменные, например - "If x>y: x,y = max,min Else: x,y = min,max"
> Дальше при каждой итерации производить операцию "If max%min ==0: N+=1"
> Ну и не забыть про ситуацию, когда x=y.
> Мимо давно не прогер.
Меньше чем O(n) решить невозможно
> Ну, раз важно быстродействие, то по-любому всё надо сделать в один цикл
Да почему она отваливается?
> О, вижу эксперта в треде. Вы такой молодец. Из тысячи двести будете тоже в цикле вычитать из восьмиста итераций?
> Пиздец ты еблан, ты ж просто нулевой.
> А по теме, нахуй писать на мпи в питоне в циклической задаче? Ну хотя че я хочу, ты ж в теме не разбираешься.
>Меньше чем O(n) решить невозможно
> Даю наводку: разность этих 2 чисел - константа. А дальше стоит поработать мозгом, а если не выходит, то идти учить арифметику основы теории чисел и делимости
Это нужно доказать.
> Либо работай с разностью двух чисел (константа же), либо с квадратным корнем большего числа. И так и так должно получиться быстро.
лол
цикл это цикл, хоть ты одну итерацию в нем делай сложность у него всеравно O(n)
Человек который дал задачу уже решил, но крысит ответ
> лол
> цикл это цикл, хоть ты одну итерацию в нем делай сложность у него всеравно O(n)
> Да, пожалуй, дальше будут ставить метку
> >которые уменьшаются на единицу одновременно, пока одно из них не станет равным нулю
> которые уменьшаются на единицу одновременно
> НА ЕДИНИЦУ
> Если ты пропустишь итерацию, то по итогу у тебя число будет 1, пропустишь две итерации, будет 2 и т.д.
> Ну и в чем проблема? В первой итерации цикла проверяешь, какое число больше, его потом целочисленно делишь на другое, если получается 0, то счётчик +1. Если оба числа равны, то счётчик можно сразу ставить равным им, ибо число на само себя всегда нацело делится.
> > должна выполняться менее чем за 1 секунду
> > 10^9
> Если оба числа будут хотя бы близки к этому самому миллиарду, то за секунду это тебе даже суперкудахтер не посчитает
> Мне кажется ОП просто придумал нерешаемую задачку и троллит двач, ибо за 125 постов ни одного решения, хотя по слухам на дваче много 300кк/нанонек погромистов
> >два целых числа
> Примем наименьшее как a, большее - как b. d = b-a.
> Тогда имеем два ряда A = (0..a) и B = A+d.
> Тогда очевидно, что чтобы член из ряда A был частным от соотв. ряда B - член из B должен быть больше или равен чем соотв. член А. Поэтому если ты и собрался проверять циклом то проверять имеет смысл только в A=(0..MIN(a,d)). Когда текущее число из ряда A > d то условие целочисленного деления (Ax+d)/Ax никогда не будет выполняться.
Ну ты гений
Если у тебя будет на вход массив из N элементов, то при том, что цикл выполняется, например, 100 раз, то это будет O(1), т.е. входные данные не влияют на время выполнения.
Если будешь проходить в цикле по каждому элементу массива (т.е. будет N итераций), то сложность будет O(n)
Если совсем примитивно объяснять
>>230747250
>Примем наименьшее как a, большее - как b. d = b-a.
>Тогда имеем два ряда A = (0..a) и B = A+d.
Тогда суть задачи сводится к следующему - сколько в ряду А чисел таких, которые при делении d на An дадут частное без остатка.
Тогда если это частное принять как x то An=d/x, а Bn=An+d=d/x+d а условие деления без остатка всегда будет выполняться - Bn/An = (d/x+d)/(d/x)=x(d/x+d)/d = d+xd/d = 1+x.
Поскольку ряд начинается с единицы - что мешает просто разделить d на a и округлить вниз? Ведь каким бы не были d и a - в ряду от 1 до a будет ровно floor(d/a) чисел которые делятся ровно, разве нет?
/тред
> Ну ты гений
> Если у тебя будет на вход массив из N элементов, то при том, что цикл выполняется, например, 100 раз, то это будет O(1), т.е. входные данные не влияют на время выполнения.
> Если будешь проходить в цикле по каждому элементу массива (т.е. будет N итераций), то сложность будет O(n)
> Если совсем примитивно объяснять
>>230749498
уже решил, но крысит ответ
Скорее всего у него также O(n)
n умноженная на любую константу это O(n)
Хоть у него и n/2 итераций, хоть n/4 это O(n) если ты не знал
> >Примем наименьшее как a, большее - как b. d = b-a.
> >Тогда имеем два ряда A = (0..a) и B = A+d.
> Тогда суть задачи сводится к следующему - сколько в ряду А чисел таких, которые при делении d на An дадут частное без остатка.
> Тогда если это частное принять как x то An=d/x, а Bn=An+d=d/x+d а условие деления без остатка всегда будет выполняться - Bn/An = (d/x+d)/(d/x)=x(d/x+d)/d = d+xd/d = 1+x.
> Поскольку ряд начинается с единицы - что мешает просто разделить d на a и округлить вниз? Ведь каким бы не были d и a - в ряду от 1 до a будет ровно floor(d/a) чисел которые делятся ровно, разве нет?
> уже решил, но крысит ответ
> Скорее всего у него также O(n)
> n умноженная на любую константу это O(n)
> Хоть у него и n/2 итераций, хоть n/4 это O(n) если ты не знал
>>230749754
Короч гугли что такое о большое
Знал естественно, но у него все нормально проходит по времени
блч сори, чет отупел с двачем этим)
a = 6
b = 10
d = b - a = 10 - 6 = 4
d / a = 4 / 6 = 0.6(6), округляем вниз = 0
охуенно ты решил братух
Фикс:
if (d == 1) return 1; можно убрать.
Как уже заметили то разница постоянна.
И большее число всегда будет разница + итератор
а меньшее просто итератор.
Успех когда большее делится на меньшее.
Вот допустим числа a b их разница b-a
нужно узнать сколько раз b-a + i
будет делиться на i
По свойству делимости это будет делиться когда b-a делится на i.
Те задача теперь звучит так: сколько делителей у числа b-a. Зная число простых делителей и количество каждого простого в разложении легко будет найти ответ. Итого нам надо найти разложение на простые множители. Простые числа на ходу считать не будем, а на считаем до выполнения основной программы и занесём в табличку. Теперь пиздохаем по табличке простых чисел и проверяем на делимость число b-a. Верхняя граница в этом цикле будет корень из b-a ибо максимум это два простых множителя одинаковых.
не убрать, а поставить перед вычислением корня, чтобы избежать вызова функции и инициализации других переменных
Простые числа тут не нужны.
Я вот как решил:
Пусть a - меньшее, b - большее;
Выделяем частный случай a = b, ответ будет равен a или b;
d = b - a
Ответом будут являться все делители числа d, которые меньше либо равны a.
Фикс: не сами делители, а их количество.
Я вот и предложил способ найти все делители числа d. Просто способом похитрее, через простые числа. А не пробой всех чисел меньше а.
Этот прав, сейчас сам прикинул. Нужно количество всех делителей разности данных чисел. Со скидкой на случаи, когда меньшее число меньше чем разность.
if (a % b == 0 .or. b % a == 0) d++
a++
b++
}
Быстрый гуглеж, впрочем, говорит, что даже при такой постановке вопроса мы не придем к О(1), а к О(n^(1/3))
https://www.geeksforgeeks.org/count-divisors-n-on13/
a--
b--
Самофикс.
Зачем О(1)? O(sqrt(n)) вполне подходит.
Количество итераций корень из d.
>>230750897
Количество итераций это количество простых чисел до корня из d.
Так шо через простые числа лучше кмк, но надо делить на простое тк оно может входить в разложение несколько раз.
А в первом способе шаг можно сделать не cnt++ а cnt+=2 после проверки на чётность.
Ну да, подойдет, ОП просто выше О(1) вроде хотел
Спасибо за задачку ОП, засабмичу ее куда надо
да питонисты, похоже, все такие
в одном из прошлых тредов такой же еблан рассказывал, что он и сумму арифметической прогрессии будет считать в цикле, потому что у него больше времени уйдет на то, чтобы "лезть в математику", чем на то, чтобы наебенить цикл.
А где считать, в рекурсии, что ли? Ты из нулевых вылез? Пиздец еблан.
Толсто.
Ну тут без выделенного облака и kubernetes не разобраться.
В жопе твоей мамаши иногда бывает толсто, даун.
С точки зрения программирования задача на уровне fuzzbuzz
На одном стуле «ряяяя это не программирование, это математика»
На другом высчитывание суммы арифметической прогрессии через цикл
На какой присаживаться?
Здесь скорее не по времени надо тестировать , а по количеству действий которое совершает алгоритм.
При таких ограничениях задача должна решаться за О(1) , то есть надо придумать формулу.
Но в реальной проге с числами вообще очень редко дело имеешь
Считай ряды объектов или операторов лол
>>230746479
>>230746486
>>230747250
>>230747718
>>230749164
какие же все программисты тупые...
в итоге всё ПО ужасно работает
>>230745508 (OP)
Это же элементарная задача, в которой нужно лишь посчитать количество делителей разницы заданных чисел
> какие же все программисты тупые...
> в итоге всё ПО ужасно работает
> Это же элементарная задача, в которой нужно лишь посчитать количество делителей разницы заданных чисел
Похож, только у меня шея тоньше и длиннее.
От тебя очень воняет яйцами, сходи подмойся.
есть годный фапконтент лень 3 часа сидеть это все выкладывать
Вишмастер же. Только ищи последнюю версию, старые с макабой не работают
Челы предоставляю вам решение за O(1)
Даны на импут два числ, пусть a и b;
Не теряя общности скажем, что всегда a >= b;(иначе просто поменяем местами)
Тогда если разница a и b == 0, ответ само число a;
если разница a и b == 1; Эти числа всегда будут взаимнопростыми пока все не придет к случаю 2:1; Ответ 1;
в остальных случаях ответ 2;
Я в ахуе...
Чет быстро написал это работает только когда b > (a/2)
Ну да, в остальном надо городить проверку за корень(
Хотя если предпосчитать простые числа до sqrt(10^9). Можно выдавать ответ за константу
нахуй ты в тред зашел? иди маняме посмотри сын пьяницы.
другой анонеще раз иди нахуй
>Это же элементарная задача, в которой нужно лишь посчитать количество делителей разницы заданных чисел
Что если первое число будет 1, а второе 9_999_999_999?
Тогда ответ будет 1
Да да уже бегу
Почему питон настолько конченный что в нём нет ++ и свитч-кейса?
Есть и то и другое