P2158 [SDOI2008]仪仗队
题目描述
作为体育委员,C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 现在,C君希望你告诉他队伍整齐时能看到的学生人数。
输入输出格式
输入格式:
共一个数N
输出格式:
共一个数,即C君应看到的学生人数。
说明
对于 100% 的数据,1 ≤ N ≤ 40000
今天看了一天的欧拉函数,明天月考放飞自我了...
对于欧拉函数
将正整数(N)用算术基本定理进行分解(N=prod_{i=1}^k{c_i}^{m_i}),(k)为(N)分解质因数后的质因子种类的个数。
则(φ(N)=N* prod_{i=1}^{k} (1-frac{1}{c_i}))
证明方法需要用到容斥原理。
几个性质:
-
若(gcd(a,b)=1),则(φ(ab)=φ(a)*φ(b))
积性函数定义啊。 -
若质数(q)满足(q|n)且(q^2|n),则(φ(q)=φ(n/q)*q)
代入定义式可以得到 -
若质数(q)满足(q|n)且(q^2 mid n),则(φ(q)=φ(n/q)*(q-1))
由积性函数性质得到 -
(sum_{d|n}φ(d)=n)
先证明是积性函数,再讨论单因子即可 -
(φ(n)*n/2=sum_{d},gcd(d,n)=1)
成对存在
在看看这题。
我们以左下角为原点,第一行为(x)轴,第一列为(y)轴。
则若点((x,y))能被看见,则((dx,dy)),(d in N^*)会被遮挡
则点((x,y))能被看见的条件为(gcd(x,y)=1),即它们互质。
那么对此,我们可以将我们要求的转换为(sum_{i=2}^n φ(i))
当然这只是右下角的一部分。
加上(0,1),(1,1),(1,0)三个点,最终答案为(3+2*(sum_{i=2}^n φ(i)))
对于欧拉函数的求和,我们可以借助线性筛的思想做到线性的复杂度
可以参考代码。
code:
#include <cstdio>
const int N=40010;
int v[N],prime[N],eu[N],cnt=0,ans=0,n;
void eular()
{
for(int i=2;i<=n;i++)
{
if(!v[i])
{
v[i]=i;
prime[++cnt]=i;
eu[i]=i-1;
ans+=eu[i];
}
for(int j=1;j<=cnt;j++)
{
int tmp=i*prime[j];
if(v[i]<prime[j]||tmp>n) break;
v[tmp]=prime[j];
eu[tmp]=eu[i]*(i%prime[j]?prime[j]-1:prime[j]);
ans+=eu[tmp];
}
}
}
int main()
{
scanf("%d",&n);
n--;
if(!n) {printf("0
");return 0;}
eular();
printf("%d
",(ans<<1)+3);
return 0;
}
2018.5.28