题解 P2158 【[SDOI2008]仪仗队】

· · 题解

这还真是道神题。。。

考虑点(x,y)在什么情况下\color{red}\text{不会}被看到

由于是从(1,1)开始看,视线应该是点A(0,0)和点B(x,y)的连线,表示为函数:

f(i)={y\over x}i

如果(x,y)不会被看到,那么这条线上一定有横纵坐标皆为整数的点,且它的横坐标小于x。

设这个点为C(x',y')

\because y'\in Z,y'={y\over x}x' \therefore {yx'\over x}\in Z

显然有一组解为({x\over gcd(x,y)},{y\over gcd(x,y)})

所以点(x,y)一定能被({x\over gcd(x,y)},{y\over gcd(x,y)})挡住。

而又有:

{x\over gcd(x,y)}\le x, {y\over gcd(x,y)}\le y

两等号成立当且仅当x\perp y。而当等号成立时,就成了自己挡住自己,显然是可以被看到的。

所以得出结论:点(x,y)当且仅当x\perp y时会被看到。

原问题转化为求:

\sum_{i=0}^{n-1} \sum_{j=0}^{n-1} [gcd(i,j)==1]

为了方便假设k就是n-1

由于gcd(0,i)=i,所以原式等于:

\sum_{i=1}^k\sum_{j=1}^k [gcd(i,j)==1]

又因为gcd(i,j)=gcd(j,i)废话,所以:

=2\cdot\sum_{i=1}^k\sum_{j=1}^{i-1} [gcd(i,j)==1]+1

之所以上面加的是1是因为前面那坨式子或漏掉点(1,1)。

我们会发现后面那坨恰好是\phi(i)。

因此式子变为:

2\cdot\sum_{i=1}^{k}\phi(i)+3

考虑如何求\sum_{i=1}^{k}\phi(i)

还是为了适应我的习惯设m为k

先引入一个没什么概念:卷积:

若:

h(n)=\sum_{d|n}f(d)g(\lfloor{n\over d}\rfloor)

则称h是f和g的卷积,写作h=f\cdot g

回到题目

众所周知:

(\phi\cdot 1)(n)=\sum_{d|n}\phi(d)=n

记h=\phi\cdot1

\sum_{i=1}^m h(i)=\sum_{i=1}^m\sum_{d|i}\phi(d) \sum_{i=1}^m h(i)=\sum_{i=1}^m\sum_{j=1}^{\lfloor{m\over i}\rfloor}\phi(d)

这一步如果不容易理解的话可以把省略掉的函数1提出来,看成交换求和号后的式子。

设:

S(n)=\sum_{i=1}^n \phi(i)

上式变为:

\sum_{i=1}^m h(i)=\sum_{i=1}^mS({\lfloor{m\over i}\rfloor}) \sum_{i=1}^m h(i)=\sum_{i=2}^mS({\lfloor{m\over i}\rfloor})+S(m) S(m)=\sum_{i=1}^m h(i)-\sum_{i=2}^mS({\lfloor{m\over i}\rfloor})

我们知道h(i)=(\phi\cdot1)(i)=i,有:

\sum_{i=1}^m h(i)=\sum_{i=1}^m i={m^2+m\over2}

即是:

S(m)={m^2+m\over2}-\sum_{i=2}^mS({\lfloor{m\over i}\rfloor})

最终答案是:

2S(n-1)+1

后面整除分块的话时间复杂度大概是:

\Theta(\sum_{i=1}^n\sqrt{\lfloor{n\over i}\rfloor})=\Theta(\int_{i=1}^n\sqrt{\lfloor{n\over i}\rfloor}di)=\Theta(n^{2\over3})

应该是最优解了吧,数据范围完全可以到MAX_INT。

对了注意的是求S(m)要先预处理出前几千的S(m),这样会更快。

还有其实快速求\phi前缀和的这个算法叫做杜教筛,不清楚可以去模版学习一下。

代码(记住1要特判):

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>

using namespace std;

typedef long long ll;

map<int, ll> sphi;
bool notprime[5001];
int t, n, prime[5001], top = 0;
ll phi[5001];

inline void pre() {
    phi[1] = 1;
    for (register int i = 2; i <= 5000; ++i) {  
        if (!notprime[i]) prime[++top] = i, phi[i] = i - 1;
        for (register int j = 1; j <= top; ++j) {  
            if (i * prime[j] > 5000) break;  
            notprime[i * prime[j]] = 1;
            if (!(i % prime[j])) {  
                phi[i * prime[j]] = phi[i] * prime[j];
                break;  
            } else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        } 
    }
    for (register int i = 2; i <= 5000; ++i) phi[i] += phi[i - 1];
}

ll calcphi(int n) {
    if (n <= 5000) return phi[n];
    if (sphi[n]) return sphi[n];
    ll rt = (ll)n * (ll)(n + 1) / 2;
    for (register unsigned int l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        rt -= (r - l + 1) * calcphi(n / l);
    }
    return sphi[n] = rt;
}

int main() {
    scanf("%d", &n); pre();
    if (n == 1) printf("0");
    else printf("%lld", 2 * calcphi(n - 1) + 1); 
    return 0;
}