Комментарии 46
Но- разверните плз вот это: s = 2r + 0.11q. Пример: q=1, r=2, получаем s=4.11 ??
PS: я бы сделал также 2 цикла и проверял, что s есть одиночное число, отличное от q и r.
Вот так получилось, немного сложнее:
for (int q = 0; q < 10; q++) {
for (int r = 1; r < 10; r++) {
if ((r != q)) {
int res = 201 * r + 21 * q;
int s = res / 100;
if (s > 0 && s < 10 && s != r && s != q) {
res -= s * 100;
if (res / 10 == q && res % 10 == r) {
System.out.println(String.format("%d%d%d+%d%d%d=%d%d%d", r, q, r, r, q, q, s, q, r));
}
}
}
}
}
(100a+20b+a)+(100a+10b+b)=100c+10b+a
201a+21b=100c+10b+a
100c=200a+11b
c = 2a + 0,11b
Кстати, из формулы s = 2r + 0.11q можно сразу сделать вывод, что q всегда равно нулю, и использовать только один цикл.
if (s % 1 == 0 && s != 0 && s < 10)
так как все цифры дадут дробный остаток при суммирование.
А это значит что можно обойтись одним циклом с проверкой на длину цифры т.е. число не большо 10
public static void main(String[] args){
int count = 0;
for (int r = 1; r < 10; r++){
double s = 2 * r ;
if (s < 10) {
count++;
}
}
}
System.out.println("count is " + count);
}
так же можно вынести проверку в if в цикл
public static void main(String[] args){
int count = 0;
for (int r = 1; 2*r < 10; r++){
count++;
}
}
System.out.println("count is " + count);
}
А так вы молодец, мало программистов женщин, так что это достойно уважения.
p.s. равное 0 мы тоже не получим так как s=2*r+0.11*q а r по условию неравно 0;
да, не заметила этот момент.
мало программистов женщинЧем эта фраза отличается от Вашей?
У нас примерно 10-20% разработчиков девушки
Те по большому счету — программа не нужна:) Раз q=0, для r остается всего (1,2,3,4), учитывая что 2*r<9
1. В первой задаче встречается сравнение двух вещественных чисел, что само по себе уже плохо. Плюс одно из чисел получено умножением на число 0,11, которое непредставимо в виде конечной двоичной дроби (то есть гарантированно будут ошибки округления). Да, в этом случае всё сработало, но так писать не стоит.
Вместо этого вполне можно было работать с целыми, используя равенство 100s = 220r + 11q. Какая разница, храним мы s в памяти или 100s? А при выводе на экран уже разделим.
Ну и в целом решение "в лоб" не хуже на самом деле. Оно отрабатывает быстро, пишется быстрее и проще в понимании. Не нужно оптимизировать то, что не тормозит. Если, конечно, не стоит цель рассказать о другом интересном решении. ;)
2. Факториал очень быстро растёт. 69! уже больше, чем 10^100. Поэтому лучше не считать его явно. (Да, кстати, в методе factorial у вас нет рекурсии.)
Вместо этого можно смотреть на делители. Я бы попробовал такой метод: раскладываем число, на которое надо делить, на простые множители, потом находим максимум из произведений множителей на степени.
Например:
5 = 5^1. m = max {5*1} = 5.
25 = 5^2. m = max {5*2} = 10.
12 = 2^2 * 3^1. m = max {2*2, 3*1} = 4.
(То есть 4! — это наименьший факториал, который делится на 12)
Почему работает, надеюсь, понятно, а то объяснять долго. (Но я сейчас это придумал сходу, может проще можно.)
На простые множители раскладывать тоже легко: делим на 2 пока делится и считаем сколько раз разделилось. Потом по нечётным числам: на 3, на 5, на 7 пока не получим единицу в частном.
Наверное, если подумать, то и S как-то можно хитро упростить, но сходу ничего в голову не приходит. Это надо серьёзно с карандашом посидеть.
3. Тоже через множители проще сделать.
А, ну да. :) Вообще, решение работает, просто не выдаёт минимальное число. Под рукой бумаги не было проверить, а поспешил с комментарием.
Тут была какая идея. Посмотреть, сколько раз (k) в факториал (m!) входит каждое простое число (p). Но я забыл что во множители факториала это число может входить несколько раз.
В реальности там сложнее, конечно:
k = [m/p] + [m/p^2] + [m/p^3] +… (квадратные скобки — округление вниз).
Нужно для каждого простого множителя найти такой m, чтобы соответствующее k равнялось степени p в разложении аргумента s(n).
В принципе, можно и перебором для m решать, так как показатели степеней не очень большие и число итераций будет не больше произведения простого множителя на его степень (как в первоначальном варианте). В любом случае быстрее вычисления факториалов, хотя решение, конечно усложняется.
И да, если продолжить рассуждения в первой задаче, то она у вас одной команде вывода ответа на экран сведётся, так как там достаточно легко все цифры вручную найти. :)
поэтому для всех числовых переменных используем тип long (иначе вычисления будут некорректными)
Неверно.
В вашей реализации, начиная с m=26, метод factorial начнет возвращать отрицательные числа.
Начиная с числа m=66, метод factorial начнет возвращать 0, после чего все проверки типа:
factorial(m) % n == 0
становятся true. Т.е. фактически, максимальный факториал, который вычисляется (притом неправильно) — это факториал от 66, что несколько меньше необходимых 2400000.
Правильный тип данных в данном случае — BigInteger.
Но как только вы замените long -> BigInteger, то вы поймете, что ваш код никуда не годится.
Вычислять факториал от двух с половиной миллионов, причем внутри двух циклов — это прямо по Горькому: «безумству храбрых поём мы славу».
rqr + rqq = sqr
На число единиц в сумме влияет только сумма единиц слагаемых, т.е. r + q = r (строго говоря — (r + q) mod 10 = r), отсюда получается, что q может быть только нулем. Далее применяя Ваши рассуждения, получаем s = 2r. Тут уже перебор сводится к единственному циклу.
Например, в первой задаче ( rqr + rqq = sqr ) очевидно, что q=0 для уравнения r+q=10x+r, при r<10, q<10, x<10; а r<5 для уравнения r+r+x = s при r<10, s<10, x<10. Тогда можно ограничиться вообще одним циклом for, в котором будем перебирать r = [1,..,4] четыре шага вместо сотни)
И вызывает подозрение третья задача — например повторения на уровне 9**2 = 3**4 можно отсечь еще до умножения (обозначим степень как **).
Метод factorial(long m) реализуем с помощью простой рекурсии: текущую переменную ret умножаем на переменную цикла for и затем присваиваем ей результат, пока не будут выполнены все итерации цикла.
У вас что-то не так с рекурсией :-)
rqr + rqq = sqr
вычитаем из левой и правой части qr
r00 + rqq = s00
отсюда q = 0, 2r = s
в итоге только один цикл for
135^135 сильно не влазит в тип, по-хорошему надо либо подумать с карандашиком либо писать длинную арифметику. Питон в той же задачке даёт 16647.
писал на питоне и перебор на 10 ядрах по моим подсчетам составлял 10 лет (=
Пришлось от брутфорса отказаться, сделать именно поиск…
P.S.
я не сильный знаток Java, но как вы на типе long можно посчитать факториал?
на С++ я уже при 25! получал переполнение 64 разрядного беззнакового типа
PS. И почитайте что такое рекурсивная функция. Факториал можно вычислить с помощью рекурсивной функции, но у вас он находится как раз через цикл.
6,596,625 = S(M, N) > sum(primes in [M, N]) > 2,300,003*6,800, что противоречиво. Прямая ошибка кроется в коде: (2*10^6)! явно не уместится в long. Также предполагаю, что решать задачу грубо вообще неприемлемо.
- Факторизируем число (раскладываем на простые множители)
- В получившемся словаре формата {prime: degree}, где prime — простое число, а degree — его степень, проходим по ключам и находим для каждого из них минимальное число n такое, что n! mod prime ^prime = 0
- Суммируем результат по всем числам в требуемом диапазоне
На моем древнем ноуте посчиталось минут за 15.
У меня считалось около 0.2 с для диапазона [5300000, 5400000]. Для вашего случая (от 630000000 до 640000000) сейчас проверил, посчиталось примерно за минуту.
Но алгоритм получения числа m придумал несколько иной:
- единожды получаем все простые числа в нужном диапазоне (в моём случае от 2 до 5400000), используя решето Эратосфена;
- раскладываем число на простые множители (пользуясь полученной таблицей простых чисел) и получаем список с множителями, причём множители могут повторяться;
- предполагаем, что число m = 1;
- для каждой группы множителей (группой назовём множители имеющие одинаковое значение) считаем количество элементов (N) в группе и выполняем следующее:
- берём первое число кратное множителю;
- делим его на множитель до тех пор, пока оно делится без остатка;
- количество раз, которое его удалось поделить, вычитаем из N;
- если N > 0, берем следующее число кратное множителю и переходим в п. 2;
- если данное число, кратное множителю, больше m, принимаем его за m и переходим к следующей группе;
Алгоритм здесь не совсем соблюдается, так как не проиходит поиск количества элементов в группе, но суть остаётся та же.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char *primes = NULL;
/* Ищет простые числа до числа count включительно.
* Поиск производится по алгоритму "решето Эратосфена".
* Возвращает 0 в случае успеха и 1 при ошибке. */
int init_primes(long count) {
primes = (char *)malloc(count + 1);
if (primes == NULL)
return 1;
memset(primes, 0xFF, count + 1);
primes[0] = 0;
primes[1] = 0;
for (long k = 2; k*k <= count; k++)
if (primes[k])
for (long j = k*k; j <= count; j += k)
primes[j] = 0;
return 0;
}
// Минимальное количество делителей, под которые будет выделена память
#define MIN_DIVS 8
/* Возвращает массив простых делителей числа n, последний элемент массива - 0 */
long *get_divs(long n) {
size_t count = 0; // Текущее количество делителей
size_t size = MIN_DIVS; // Размер массива с делителями
long *divs = (long *)calloc(size, sizeof(long));
if (divs == NULL) {
fprintf(stderr, "Error: memory allocation failure\n");
exit(1);
}
long div = 2;
while (n != 1) {
if (primes[n]) {
if (count == size - 1)
divs = realloc(divs, (size << 1) * sizeof(long));
divs[count] = n;
return divs;
}
if (n % div) {
while (!primes[++div]);
continue;
}
// Если текущего размера массива не хватает, выделим ещё памяти
// помним так же, что в конце должен быть ноль (поэтому вычитаем 1)
if (count == size - 1) {
divs = realloc(divs, (size <<= 1) * sizeof(long));
if (divs == NULL) {
fprintf(stderr, "Error: memory reallocation failure\n");
exit(2);
}
}
divs[count++] = div;
n /= div;
}
return divs;
}
/* Реализация функции s(n), данной в задании.
* Для числа n ищет число m такое, что m! без остатка делится на n. */
long min_factorial(long n) {
long *divs = get_divs(n);
long *div = divs;
long prev_div = *div;
long max = 1;
while (*div) {
long k = *div;
while (*div == prev_div) {
if (k > max)
max = k;
long t = k;
while (*div == prev_div && t % *div == 0) {
t /= *div;
div++;
}
if (*div != prev_div)
break;
k += *div;
}
prev_div = *div;
}
free(divs);
return max;
}
int main(void) {
if (init_primes(5400000)) {
printf("Primes initialization error\n");
return 1;
}
unsigned long sum = 0;
for (long l = 5300000; l <= 5400000; l++)
sum += min_factorial(l);
printf("%lu\n", sum);
free(primes);
return 0;
}
Надо переделать.
Поскольку JAVA не знаю, писал на питоне:
def foo(a1, a2, b1, b2):
s = set()
for a in range(a1+1, a2):
for b in range(b1+1, b2):
s.add(pow(a, b))
return len(s)
Это против 30 строк у автора статьи.
pow(double a1, double a2, double b1, double b2)
можно реализовать на добавлении элементов в HashSet, чтобы сразу же удалить все повторяющиеся элементы, тогда он тоже будет содержать всего шесть строк (убираем все строки, добавляющие наглядности). Не зря же Python отличается своей краткостью :)
a1^b1 == a2^b2, если a1 = a2^k, b2 = b1*k.
То есть, берём 132*132 клеточки, и для каждого a прореживаем a^2,b=2i, a^3,b=3i,…
Поскольку клеточек у нас мало, то вот такое простое решето с массивом и подсчётом количества оставшихся клеточек — оно и быстро, и просто.
bool ab[135][135] = {}; // заполнено значениями false - т.е. "не покрашены ещё"
for(int a1=3; a1 < 135; ++a1) {
for(int b1=2, a2=a1*a1; a2 < 135; b1+=1, a2*=a1) { // бежим по степеням числа a1
for(int b2=b1; b2 < 135; b2+=b1) { // красим кратные степени
ab[a2][b2] = true; // "повторно использовано"
}}}
int count = 0;
for(int a1=3; a1 < 135; ++a1)
for(int b1=3; b1 < 135; ++b1)
if(!ab[a1][b1])
++count;
Можно обойтись без таблицы, а посчитать, сколько дубликатов следует выкинуть.
Для больших диапазонов так и следует поступать…
Теперь я понимаю, что с большими числами нужно быть аккуратнее.
Только надо понимать, что 134^134 — это очень большое число, и оно не влезет в double.
Поэтому
1) вместо a^b берём логарифм: log(a^b) = log(a)*b, где основание логарифма — по вкусу. Пусть даже натуральное
2) прикидываем, какая точность нам нужна.
Логарифмы 3..134 лежат на отрезке [1.0;5.0] и отличаются в 4 разряде; и умножаем на 3-значное число — то есть, нам, как минимум, 4+3 = 7 десятичных разряда нужны, чтобы не получить ложноположительный вердикт (признать неравные числа равными).
С другой стороны, в 4 младших десятичных разрядах мантиссы размножается мусор — при умножении на максимум 134. Если мы не будем их отбрасывать, то получим ложноотрицательные вердикты (признаем равные числа неравными).
А у double размер мантиссы — 16 десятичных разрядов. Отбросим 4 — останется 12, этого с избытком хватает для нашего случая.
Таким образом, — тада, делаем множество.
#include <iostream>
#include <set>
#include <cmath>
// сигнатура - некоторое число, уникально идентифицирующее нашу a^b
// в данном случае, это логарифм степени, как я уже сказал выше
double signature(int a, int b) {
return floor(log(a) * b * 10000000); // возьмём 7 разрядов после запятой
}
int main() {
std::set<double> signatures;
for(int a = 3; a < 135; ++a) {
for(int b = 3; b < 135; ++b) {
double s = signature(a,b);
signatures.insert(s);
}
}
std::cout << signatures.size() << " уникальных чисел" << std::endl;
}
Получаем 16515.
Вторая и третья задача содержат факториал и степени на больших числах, что уже должно останавливать от попытки решать тупым перебором.
Во второй надо разложить на множители x1^s1, ..., xk^sk: т.е. надо s1 штук x1,… И надо перебирать от 1 и далее числа, так же раскладывая на множители, и вычитать соответствующее количество, пока требуемое число si для всех xi не наберем. И так для диапазона чисел.
Третий если перебирать то хотя бы как в https://habrahabr.ru/post/311908/#comment_9851084
Иначе можно разложить на множители число A и кодировать степени в строку и вставлять строки в контейнер. Пример: 6^3=2^3*3^3, или 8^3=2^9.
Строим массив простых чисел до N включительно. Если это не сделать, то разложение миллиона чисел на простые множители будет дорогой операцией (у меня на питоне это занимало 8 против 175 секунд).
Надеюсь, не надо рассказывать, как просеивать числа за O(sqrt(n))?
Далее, для каждого числа n из [M;N] делаем следующее:
Раскладываем на простые множители. Даже не в виде пар «множитель, степень», а просто все множители подряд.
Т.е. 240000 = [2, 2, 2, 2, 2, 2, 2, 3, 5, 5, 5, 5]
Самое длинное разложение будет для 2^18 = 262144 :)
Мысленно строим факториалы m! от 1 до много-много
Каждое умножение на m — это мысленное добавление новых простых множителей.
Просто берём и вычёркиваем эти множители из исходного разложения.
[2, 2, 2, 2, 2, 2, 2, 3, 5, 5, 5, 5]
2 :: [2, 2, 2, 2, 2, 2, 3, 5, 5, 5, 5]
3 :: [2, 2, 2, 2, 2, 2, 5, 5, 5, 5]
4 :: [2, 2, 2, 2, 5, 5, 5, 5]
5 :: [2, 2, 2, 2, 5, 5, 5]
6 :: [2, 2, 2, 5, 5, 5] и множитель 3 мы проигнорировали
7 :: ничего не вычеркнули
8 :: [5, 5, 5]
9 :: ничего
10 :: [5, 5] — а все 2 ещё раньше кончились
11
12
13
14
15 :: [5]
20 :: [] — о, победа!
Таким образом, s(240000) = 20.
Но бежать по m подряд очень опасно:
230000 = [2, 2, 2, 2, 5, 5, 5, 5, 23]
230001 = [3, 76667] — ого, какой перерывчик будет
230002 = [2, 115001] — а здесь ещё больше
230003 = [230003] — а тут вообще простое число, s(230003) = 230003
230004 = [2, 2, 3, 3, 6389]
Поэтому делаем следующим образом
Вычёркиваем множители, входящие в m
Находим следующее m' > m, делящееся хоть на один из наших множителей
— для каждого множителя строим гипотезу m' = m + (p — m mod p) — т.е. ближайшее округлённое вверх
— среди этих гипотез выбираем минимум
230000 = [2, 2, 2, 2, 5, 5, 5, 5, 23]
2 :: [2, 2, 2, 5, 5, 5, 5, 23] ==> m' = min{4, 5, 23} = 4 — про 3 ни слова
4 :: [2, 5, 5, 5, 23] ==> m' = min{6, 5, 23} = 5 — обратите внимание, что минимум достигнут не на младшем множителе
5 :: [2, 5, 5, 23] ==> m' = min{6, 10, 23} = 6
6 :: [5, 5, 23] ==> m' = min{10, 23} = 10
10 :: [5, 23] ==> m' = min{15, 23} = 15
15 :: [23] ==> m' = min{23} = 23
23 :: []
s(230000) = 23.
На всякий случай, — сходу отвергнем гипотезу, что s(n) равно максимальному простому множителю или что-то в таком роде.
230187 = [3, 277, 277] — s = 554 (=227*2)
230318 = [2, 11, 19, 19, 29] — s = 38 (вообще не делится на 29)
Ну вот. Когда мы научились быстро находить s для любого числа (не превосходящего N, потому что простые числа мы только дотуда нагенерировали),
осталось только пробежать по всему диапазону [M,N] и просуммировать.
Мы потратим на это всё время порядка O((N-M) * log(N)^2).
Ну и O(N*sqrt(N)) на таблицу простых чисел.
Заметьте! Ни длинная арифметика, ни тугие забеги за квадратичное время не понадобились.
Разбор задач заочного тура школы программистов HeadHunter 2016. Часть 1