spoj NAJPWG 的解决方案。给出 TLE

Question

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

但我不知道这里还应该做些什么优化来避免TLE。我还阅读了 euler totient 函数，但无法真正理解该方法。我已经阅读了 4 种计算欧拉 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。

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

披函数是O(n^2)？真的吗？至少在我的代码中，我不认为它是 O(n^2)
GCD不需要功能
这是一道简单的数学/数论题，不是DP题
预计算，预计算，预计算！你可以预先计算很多东西，比如为每个输入 n 循环，你可以只在 O(1)!
先学习素筛和算术基本定理，然后再研究 Phi 函数。（或者你只要记住Phi函数的公式，确实很容易记住）

Answer 2

好吧，我认为更好的方法是根据 Euler 的 Totient 函数来考虑它... Totient 函数为您提供低于数字 n 且与其互质的数字的数量，即 GCD(n,x )=1 其中

x < n .

现在 pairs till n 是 Pairs till n-1 + Pairs with n 即（n- n 的 Totient 函数）。

Totient函数参考Link

我认为您需要借助 Totient Sieve 将每个数字的总和预处理到 10^6，因为 N* 根 (N) 不会及时通过。

spoj NAJPWG 的解决方案。给出 TLE

solution of spoj NAJPWG. Gives TLE

c

algorithm

greatest-common-divisor