Избегайте ограничения по времени нечетного числа нечетных делителей - PullRequest
Новая
       17

Избегайте ограничения по времени нечетного числа нечетных делителей

0 голосов
/ 05 октября 2018

Задача была на соревновании: учитывая диапазон [L, R], найдите число целых чисел в этом диапазоне, которые имеют нечетное число нечетных делителей.Например, 1 имеет только один делитель, и он нечетный, 9 имеет три делителя {1, 3, 9}, и все они нечетные.Между тем, 18 имеет шесть делителей {1, 2, 3, 6, 9, 18}, но три из них странные.Таким образом, 1, 9 и 18 имеют нечетное количество нечетных делителей.

Вход Вход будет начинаться с положительного целого числа T (T ≤ 10 5), обозначающего количество тестовых случаев.Каждый тестовый случай будет иметь два натуральных числа L, R (1 ≤ L ≤ R ≤ 10 18), диапазон.

Выход Для каждого теста первая строка будетбыть номером дела в формате «Case t: x» без кавычек.Здесь t - это номер дела, начиная с 1, а x - это число целых чисел, попадающих в диапазон [L, R] и имеющих нечетное количество нечетных делителей.

Образец 

Input   Output

3

1 3

5 10

10 15   


Case 1: 2

Case 2: 2

Case 3: 0

Что я кодирую: 

#include <bits/stdc++.h>
#include <cmath>
using namespace std;

int main()
{
    int T;
    cin>>T;

    for(int j=0; j<T; j++)
    {
        int m, nx;
        cin>>m>>nx;
        int finalCount = 0;

        for(int kk=m; kk<nx; kk++) // number
        {
            // Note that this loop runs till square root
            int oddCounter = 0;
            for (int i=1; i<=sqrt(kk); i++)
            {
                if (kk%i == 0)
                {
                    // If divisors are equal, print only one
                    if (kk/i == i)
                    {
                        if (kk & 1)
                            oddCounter++;
                    }
                    else // Otherwise print both
                    {
                        if (i & 1)
                            oddCounter++;
                        if ((kk/i) & 1)
                            oddCounter++;

                    }
                }
            }

            if ( oddCounter& 1)
                finalCount++;
        }

        cout<<"Case "<<j+1<<": "<<finalCount<<"\n";

    }

    //auto var_name = 0;
    //cout<<var_name<<"\n";

}

Но превышен лимит времени. 

CPU: 2s

Memory: 1500MB

Как я могу улучшить свой код?Любое предложение?

...