首页 > 代码库 > 【BZOJ】2190: [SDOI2008]仪仗队（欧拉函数）
【BZOJ】2190: [SDOI2008]仪仗队（欧拉函数）
http://www.lydsy.com/JudgeOnline/problem.php?id=2190
一开始没想到QAQ看了题解恍然大悟，虽然做法和题解不同。。
因为以1开头或结尾的坐标的比较特殊，所以首先不考虑先。
考虑从2开始的坐标，发现当这个点不在以点(1,1)放出的射线第一个遇到的点时，则不选。意思就是说，不是第一个点的倍数！
因此想到当坐标gcd(x, y)!=1时，这个点看不到！因为d=gcd(x, y)!=1，显然有坐标(x/d, y/d)在这条线上！（可以用斜率来搞搞。。但是这是显然的吧。。）
然后发现似乎有点难算？比如有些点(4, 2)虽然看得到但是gcd(4, 2)=2，问题出在哪？(2, 1)本来就不在射线上！
将坐标全部减1....
然后你会发现行了。。。。。。。。。。。。。。。。。。。。。。。。。。
然后答案就是
$$\sum_{x=1}^{n-1} \sum_{y=1}^{n-1} [gcd(x, y)=1]$$
这个是莫比乌斯的特例。。。。。。直接欧拉函数可以上。。。。
就是
$$\sum_{1<=i<=n-1} \phi(i)$$
然后乘个2，因为1,1算了两次，因此减1，然后原版坐标1,1旁边有两个，所以+2，所以答案就是
$$1+2\sum_{1<=i<=n-1} \phi(i)$$
#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }#define rdm(x, i) for(int i=ihead[x]; i; i=e[i].next)const int N=40005;int p[N], cnt, np[N], phi[N];void init(int n) { phi[1]=1; for1(i, 2, n) { if(!np[i]) p[++cnt]=i, phi[i]=i-1; for1(j, 1, cnt) { int t=p[j]*i; if(t>n) break; np[t]=1; if(i%p[j]==0) { phi[t]=phi[i]*p[j]; break; } phi[t]=phi[i]*phi[p[j]]; } }}int main() { int n=getint(); init(n-1); int ans=0; for2(i, 1, n) ans+=phi[i]; ans=ans*2+1; print(ans); return 0;}
Description
作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 
现在，C君希望你告诉他队伍整齐时能看到的学生人数。
Input
共一个数N。
Output
共一个数，即C君应看到的学生人数。
Sample Input
Sample Output
HINT
【数据规模和约定】 对于 100% 的数据，1 ≤ N ≤ 40000
Source
数论
【BZOJ】2190: [SDOI2008]仪仗队（欧拉函数）