优化代码

wxhhpsmaq__ @ 2024-11-01 22:51:17

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n;
    cin >> n;
    long long ans = 0;
    while (n > 0)
    {
        ans++;
        long long cnt = 0;
        for (long long i = 1; i <= ans; i++)
            if (ans % i == 0)
                cnt++;
        if (cnt % 2 == 0)
            n--;
    }
    cout << ans;
    return 0;
}

by QWQ_HY_DFX @ 2024-11-01 23:04:53

@wxhhpsmaq__ 你这是要求第n个因子个数是偶数的数吧

by QWQ_HY_DFX @ 2024-11-01 23:09:34

@wxhhpsmaq__

对于x = \displaystyle\prod\limits_{i = 1}^{k}{p_i^{c_i}}，显然其因子个数d(x) = \displaystyle\prod\limits_{i = 1}^{k}{(c_i+1)}

考虑d(x)为奇数的情况,显然当且仅当c_i均为偶数时d(x) = 1,此时x为完全平方数

也就是说,其实是要你求出一个最小的x,满足x减去x内的完全平方数的数量为n,也就是x-\lfloor\sqrt{x}\rfloor = n

说到这应该会做了吧...

by QWQ_HY_DFX @ 2024-11-01 23:53:18

@wxhhpsmaq__

直接枚举完全平方数个数O(\sqrt{n})已经能过了，不过可以再优化一下

考虑枚举完全平方数个数i的过程，这里要满足n+i \ge i^2且n+i < (i+1)^2

考虑取等号时的解，舍去负根，根据不等号，得到解的区间为(\cfrac{\sqrt{4n-3}-1}{2},\cfrac{\sqrt{4n+1}+1}{2}]，取最小正整数解即可

最后输出最小正整数解+n即可，时间复杂度O(1)

不过看这n \le 10^{15}估计出题人想的正解就是O(\sqrt{n})

by QWQ_HY_DFX @ 2024-11-02 10:46:07

好吧第二条出了点事，d(x)不是等于1是为奇数，笔误(

by wxhhpsmaq__ @ 2024-11-02 11:52:40

@QWQ_HY_DFX 求代码

by QWQ_HY_DFX @ 2024-11-02 12:11:58

@wxhhpsmaq__ emm...

所以这是哪里的题啊

不是这东西不是写得清清楚楚吗直接照着打不就行了