Кајгана CodeOpen. Reopened!

[back_rest]

Задача numero uno: Кул делители

Позитивен цел број k поголем од нула се нарекува кул делител на m ако е помал од m и делител на m, но k^n не е делител на m. Нека d(m) е функција која означува број на кул делители за бројот m. Ако се дадени два цели броеви a и b, да се напиште функција која ќе го врати резултатот на: d(a) + d(a+1) + d(a+2) + ... + d(a+b). Дадени параметри се a, b и n.

a може да биде од 1 до 1000000
b може да биде од 1 до 10000000
n може да биде од 2 до 10

Резултатот е гарантирано во рамките на големината на 32bit integer

Влезни параметри: int a, int b, int n
Функција: int coolDivisors(int a, int b, int n)

Примери:

coolDivisors(1, 12, 2) = 8
coolDivisors(1000000, 10000000, 10) = 146066338

Тест случаеви:

coolDivisors(100, 1000, 3) = ?
coolDivisors(1000, 10000, 4) = ?
coolDivisors(10000, 100000, 5) = ?

Бидејќи задачата е од средна категорија, имате 24 часа за решавање

 

[Димитар]

Moже малку подобро објаснување што се тоа кул делители.

Прилично конфузно си објаснил...

 

[диме]

Аууу срам да ми е.... го дадов и кодот. Се надевам не го копира некој

Хех само ако вредностите на аргументите се поголеми се чека многуууу

coolDivisors(100, 1000, 3) = 5208
coolDivisors(1000, 10000, 4) = 76202
coolDivisors(10000, 100000, 5) = 996600

 

[јас]

Тест резултати :wink::

coolDivisors(100, 1000, 3) = 5208
coolDivisors(1000, 10000, 4) = 76202
coolDivisors(10000, 100000, 5) = 996600

едит: Изгледа втор сум
п.с диме колку е то многу? за максимумите на ксило.... ме фати 5 секунди (и нешто ситно)

 

[back_rest]

Moже малку подобро објаснување што се тоа кул делители.

Прилично конфузно си објаснил...

Еве примерот: coolDivisors(1, 12, 2) = 8

1,2,3 - прости броеви

4.
делители (k) : 2
k^n : 4 - делив со 4(m) => 2 не е кул делител на 4

5 - прост

6.
делители : 2, 3
k^n: 4, 9 => не се делители на 6 => 2, 3 кул делители на 6

7 - прост
8.
делители: 2, 4
k^n: 4, 16 =>16 не е делител на 8 => 4 е кул делител на 8

9.
делител 3
k^n: 9 => 3 не е кул делител на 9

10. кул делители: 2, 5
11. прост
12. кул делители 3, 4, 6
13. прост

вкупно: 8 кул делители.

@диме, чувај си го кодот

Хех само ако вредностите на аргументите се поголеми се чека многуууу

п.с диме колку е то многу? за максимумите на ксило.... ме фати 5 секунди (и нешто ситно)

Ќе ве научам јас вас да штедите на комплексност .
5 секунди е цела вечност за решавање на ваков проблем. Оптимизирано решение треба за најгломазниот пример да даде резултат во редот од 1/10 од секунда па дури и помалце.

Чисто за поука: brute force постои за секој проблем и ќе даде точен резултат. Прашање е на време: секунди, минути, години . Уметноста е да се најде конкретниот пристап. Ајде сега мисле малку ако некој ги сака трите поени.

 

[Bacillus gagous]

Абе на припреми за државен програмирање во втора година средно имаше едни задачи со земјата инфодонија во која владеел инфокралот. Дај им жити се Хсиломедиус некоја од овие задачи.

 

[Димитар]

ОК, сфатено...

истите резултати
CoolDivisors(100, 1000, 3) = 5208
CoolDivisors(1000, 10000, 4) = 76202
CoolDivisors(10000, 100000, 5) = 996600

и истиот проблем со брзината

Ако стигнам до вечер, ќе пробам да оптимизирам малку

 

[loverboy]

Ја решив и јас. Истите резултати се добиваат како што кажа Димитар

CoolDivisors(100, 1000, 3) = 5208
CoolDivisors(1000, 10000, 4) = 76202
CoolDivisors(10000, 100000, 5) = 996600

Исто проблем е брзината. Околу 6 секунди му треба да пресмета
coolDivisors(1000000, 10000000, 10) = 146066338

Ќе се обидам да оптимизирам сега,
Поздрав

 

[loverboy]

Прва оптимизација, успеав да намалам на 1 секунда за "најбавниот пример". После ќе се обидам уште да оптимизирам на помалку од секунда.

 

[deXterche]

CoolDivisors(100, 1000, 3) = 5208
CoolDivisors(1000, 10000, 4) = 76202
CoolDivisors(10000, 100000, 5) = 996600

Оптимизација фаза

 

[Vnuce]

Мислиш... bug fixing фаза

 

[back_rest]

Уште само 2 часа. Бидете спремни во 00:00 да ги праќате кодовите.

 

[back_rest]

Ајде доста ви беше. Чекам до 01:00 кодови.

 

[Димитар]

private int CoolDivisors(int a, int b, int n)
{
int brojac = 0;
for (int i = a; i <= (a+b); i++)
for (int j = 2; j <= i/2; j++)                
if ((i % j == 0))                       
if (i % Math.Pow(j, n) !=0)
brojac++;
return brojac;
}

 

[јас]

Уште истото од вчера (линеарна). Баш ме интересира шо математика ќе извајш

    public int coolDivisors(int a, int b, int n){
        int top = a+b;
        int tmp=0;
        for (int i = 2; i <= top/2; i++) {
            tmp+=(top/i)-((a-1)/i);
            int p = (int)Math.pow(i, n); 
            tmp-=(top/p)-((a-1)/p);
        }        
        int m = Math.max(2,a); 
        tmp-=(top/2)-m+1;
        return tmp;
    }