0

问题集是一场竞赛：给定一个范围 [L, R]，找出该范围内具有奇数个奇数除数的整数个数。​例如1只有一个除数是奇数，9有三个除数{1, 3, 9}都是奇数。同时，18 有六个除数 {1, 2, 3, 6, 9, 18} 但其中三个是奇数。所以 1、9 和 18 有奇数个奇数除数。

输入 Input 将以正整数 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

如何改进我的代码？有什么建议吗？

4

0 回答 0