Программаның әрбір тестіге жауап беру уақыты 2 секундтан аспайды

   Берілген b натурал саны а санына қалдықсыз бөлінсе, онда а саны b санының бөлгіші болады. Мысалы, 15 санының 4 бөлгіші бар: 1, 3, 5, 15. Әрбір берілген b саны үшін оның бөлгіштер саны жұп немесе тақ сан болатынын анықтаңдар. Берілген N (1 < N <= 105) және b саны берілген. Әрбір берілген b (1 <= b <= 1018) үшін бөлгішінің саны жұп сан болcа 0, бөлгіші саны тақ сан болса 1 санын шығар.

   Тестілеуге тоқталайық. Бұл тестілер есеп шығарудан бұрын, алдын ала дайындалып ұсынылады. Есептің жалпы саны 10 тест болғанымен, сендермен негізгі 5 тестке тоқталамыз. Себебі бірдей типтегі тестілер 2 реттен қайталанған.

   Есептің тестілері неге бұлай берілген? Есепті шешуде қандай қиындық кездеседі?

   Есепті шешуде бір санның бөлгішін табу үшін бізге бір параметрлі цикл, ал сандар тізбегінің бөлгішін табу үшін тағы бір цикл қосуымыз қажет. Сонда бұл есепті орындау үшін кіріктірілген 2 цикл пайдалануымыз керек болады. Ал берілетін сандар тізбегінің ұзындығы 100000 екенін ескерсек, онда программа әр тестіге 2 секундтта жауап беруі мүмкін емес.

   Бұл жерде туындайтын 2-ші мәселе b санының шегі 1018. Біз санның бөлгішін анықтауда санды сол санның жартысына дейінгі сандарға бөліп шығамыз (алдыңғы тақырып). Олай болса, біз бұл санның жартысына дейін циклді айналуымыз тіпті де мүмкін емес. Өзіміз білетін алгоритм арқылы шешу есепті 20% ғана орындауға мүмкіндік береді деген сөз. Демек, бұл есепті шешудің басқа тиімді алгоритмін қарастыруымыз қажет. Бұл есепке қолданатын тиімді алгоритм ретінде берілген саннан √b квадрат түбір алу қажет. Егер сан квадрат түбірден бүтін шығатын болса, онда бұл санның бөлгіштері тақ сан, әйтпесе жұп сан болады.

   Мысалы: 36-дан квадрат түбірден 6 шығады. Оның бөлгіштері саны 9: 1, 2, 3, 4, 6, 9, 12, 18, 36. Ал, 40-тан түбір 6,324.... Оның бөлгіштер саны 8: 1, 2, 4, 5, 8, 10, 20, 40.

 Сұрақтар

1. Программаны тестілеу дегеніміз не?

2. Программаны тестілеу қандай кезеңдерден тұрады?

3. Тестілеу барысында қандай қате түрлерін анықтауға болады?