Чем мне нравится Project Euler - практически на любой задаче можно что-то для себя открыть/переоткрыть.
The radical of n, rad(n), is the product of distinct prime factors of n. For example, 504 = 23 × 32 × 7, so rad(504) = 2 × 3 × 7 = 42.
We shall define the triplet of positive integers (a, b, c) to be an abc-hit if:
1. GCD(a, b) = GCD(a, c) = GCD(b, c) = 1
2. a < b
3. a + b = c
4. rad(abc) < c
For example, (5, 27, 32) is an abc-hit, because:
1. GCD(5, 27) = GCD(5, 32) = GCD(27, 32) = 1
2. 5 < 27
3. 5 + 27 = 32
4. rad(4320) = 30 < 32
It turns out that abc-hits are quite rare and there are only thirty-one abc-hits for c < 1000, with ∑c = 12523.
Find ∑c for c < 110000.
После некоторого достаточно бесплодного с точки зрения результата размышления(о котором тоже в принципе интересно было бы написать) я пришел к решению проблемы практически "в лоб" - перебираем все числа a b c такие что a<b,a+b=c и с<110000
и проверяем выполняются ли для них условия 1. и 4.
Код:
int count = 0;
ulong64 sum = 0;
for(int a=1;a<limit ;++a){
int b = a+1;//a < b
int c = a+b;//c = a + b
while(c<limit){
if( ! (cross(dpf[a],dpf[b]) || cross(dpf[a],dpf[c]) || cross(dpf[b],dpf[c]))){//GCD(a, b) = GCD(a, c) = GCD(b, c) = 1
if(rad[a]*rad[b]*rad[c]<c_long){//rad(abc) < c
++count;
sum+=c;
}
}
c = a+(++b);
}
}
Здесь dpf[i] - массив из простых делителей числа i (например для 504 это будет [2,3,7])
rad[i] - произведение все чисел из массива dpf[i].
Функция cross(a,b) возвращает false если массивы a и b не пересекаются, т.е. нет такого числа i входящего одновременно в оба массива.
соответственно
if( ! (cross(dpf[a],dpf[b]) || cross(dpf[a],dpf[c]) || cross(dpf[b],dpf[c]))){
соответствует условию
1. GCD(a, b) = GCD(a, c) = GCD(b, c) = 1
Далее из этого же условия следует что rad(a*b*c) == rad(a)*rad)b)*rad(c), соответственно
if(rad[a]*rad[b]*rad[c]<c_long)
соответствует условию
4.rad(abc) < c
Вообщем надеюсь логика более менее понятна. На тестовом условии (для c<1000 count == 31 и sum == 12523) этот подход отрабатывал. Оставалась мелочь - запустить его же для c<110000.
Первая проблема была - ну оооочень долго выполняется. Когда спустя минут 10 я добрался до a=4000 я прервал выполнение.
Первая попытка оптимизации - если а и b четные их можно не проверять. Поэтому добавилось условие
if(a%2 == 1 || b%2 == 1)
Все равно очень долго...да и явно неправильный результат.
В чем проблема? переполнение... переполнение может происходить при проверке условия rad(a)*rad)b)*rad(c). Переходим к unsigned long long. Результат вроде становится правильным...но все равно ооочень долго.
Хм...хм...
Возможно кому-то решение видно сразу. Я думал достаточно долго. Даже было желание вновь придумать другой подход.
В результате прогнав несколько тестов (на меньшем значении c) я понял в чем дело.
Во внутреннем цикле используются два условия - 1. и 4. Результат должен удовлетворять обеим условиям. С этой точки зрения условия равнозначны. Но - они не равнозначны с точки зрения времени выполнения и частоты срабатывания.
Условие 4. срабатывает реже чем условие 1. И в то же время выполняется намного быстрее.
Поэтому все что нужно - поменять условия 1. и 4. местами...
Результат (я убрал переход к unsigned long long для наглядности):
int count = 0;
ulong64 sum = 0;
for(int a=1;a<limit ;++a){
int b = a+1;//a < b
int c = a+b;//c = a + b
while(c<limit){
if(a%2 == 1 || b%2 == 1){
if(rad[a]*rad[b]*rad[c]<c_long){//rad(abc) < c
if( ! (cross(dpf[a],dpf[b]) || cross(dpf[a],dpf[c]) || cross(dpf[b],dpf[c]))){//GCD(a, b) = GCD(a, c) = GCD(b, c) = 1
++count;
sum+=c;
}
}
}
c = a+(++b);
}
}
Время выполнения стало 29 секунд.
Выводы.
Порядок выполнения проверок имеет значение... Вывод в общем то очевидный. Но про него часто забывают.
Кстати, родилась простая задачка которую можно использовать на собеседованиях.
Есть два отсортированных по возрастанию массива целых чисел. Определить пересекаются ли эти массивы за время O(n+m), где n и m - длина массивов.