题解 P2158 【[SDOI2008]仪仗队】
Smallbasic · · 题解
这还真是道神题。。。
考虑点(x,y)在什么情况下
由于是从(1,1)开始看,视线应该是点A(0,0)和点B(x,y)的连线,表示为函数:
如果(x,y)不会被看到,那么这条线上一定有横纵坐标皆为整数的点,且它的横坐标小于x。
设这个点为
显然有一组解为
所以点
而又有:
两等号成立当且仅当
所以得出结论:点(x,y)当且仅当
原问题转化为求:
为了方便假设k就是
由于
又因为废话,所以:
之所以上面加的是1是因为前面那坨式子或漏掉点(1,1)。
我们会发现后面那坨恰好是
因此式子变为:
考虑如何求
还是为了适应我的习惯设
先引入一个没什么概念:卷积:
若:
则称
回到题目
众所周知:
记
这一步如果不容易理解的话可以把省略掉的函数1提出来,看成交换求和号后的式子。
设:
上式变为:
我们知道
即是:
最终答案是:
后面整除分块的话时间复杂度大概是:
应该是最优解了吧,数据范围完全可以到MAX_INT。
对了注意的是求
还有其实快速求
代码(记住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;
}