c - spoj NAJPWG 的解决方案。给予 TLE

Question

问题的链接是 - spoj question

我尝试通过这种方法解决问题 - N 范围内的对数 = N-1 范围内的对数 + 一些新对。

但我不知道这里还应该做哪些优化来避免 TLE。我还阅读了有关 euler totient 函数的内容，但无法真正理解该方法。我已经阅读了 4 种计算 euler phi 的方法，但我猜它们都需要相同的 O(n^2)。

P.S - 我只想知道有关进一步方法而不是直接解决方案的提示。提示就可以了。预先非常感谢。

这个问题的代码是 -

#include<stdio.h>
typedef unsigned long long int ull;
ull a[100000] = {0};

inline ull g()
{
    ull n=0;
    char ch;
    ch = getchar_unlocked();
    while(ch < '0' || ch > '9')
        ch = getchar_unlocked();
    while(ch >= '0' && ch <= '9') {
        n = (n<<3) + (n<<1) + (ch - '0');
        ch = getchar_unlocked();
    }
    return n;
}

ull gcd( ull a , ull b)
{
    if(b == 0)
        return a;
    else 
        return gcd(b , a % b);
}

ull find(ull n)
{
    if(n == 0 || n == 1)
        return n;
    else if(a[n] != 0)
        return n;
    else
        return find(n-1);
}

ull range(ull n)
{
    ull c, i, nf,t;
    nf = find(n);
    c = a[nf];
    t = nf;
    nf++;
    while(nf <= n) {
        a[nf] = a[t];
        for(i = 2 ; i <= nf ; i++) {
            ull gd = gcd(i,nf);
            if(gd > 1) {
                c++;
                a[nf]++;
            }
        }
        nf++;
    }
    return c;
}

int main()
{
    ull t = g();
    ull i = 1;
    while(t--) {
        ull n = g();
        if(a[n] == 0)
            a[n] = range(n);
        printf("Case %llu: %llu\n",i++,a[n]);
    }   
    return 0;
}

Answer 1

去尝试一下，就得到了空调。

正如您所说的仅提示，这里有一些基于我的 AC 解决方案和您的尝试:

1. Phi 函数的复杂度是O(n^2)？真的吗？至少在我的代码中，我不认为它是O(n^2)
2. 不需要GCD函数
3. 这是一个简单的数学/数论问题，而不是 DP 问题
4. 预计算，预计算，预计算!您可以预先计算很多东西，例如对每个输入n进行循环，您可以在O(1)中输出答案!
5. 在研究 Phi 函数之前，请先学习素筛和算术基本定理。 (或者你可以只记住Phi函数的公式，确实很容易记住)