P2158[SDOI2008]仪仗队
(Description)
有一个(n imes n(1leq nleq 40000))的点阵，每个点上有一个人，问站在左下角的人视线中能看到多少人。
(Solution)
除去((1,0)和(0,1))两个点，对答案有贡献的其它点都满足(Gcd(x,y)=1)。那么(ans=sum_{i=1}^{n-1}sum_{j=1}^{n-1}[gcd(i,j)=1]+2)。
容易看出第一项与第三项的值相等，第二项为1。所以(ans=2 imessum_{i=1}^{n-1}sum_{j=1}^{i-1}[gcd(i,j)=1]+1+2=2 imessum_{i=2}^{n-1}+3=2 imessum_{i=1}^{n-1}phi(i)+1)。
#include<complex>
#include<cstdio>
using namespace std;
const int N=4e4+7;
int n,tot,ans;
int prime[N],phi[N];
bool check[N];
void Euler()
{
check[1]=phi[1]=1;
for(int i=2;i<=n;i++)
{
if(!check[i])prime[++tot]=i,phi[i]=i-1;
for(int j=1;j<=tot && i*prime[j]<=n;j++)
{
check[i*prime[j]]=1;
if(i%prime[j])phi[i*prime[j]]=phi[i]*phi[prime[j]];
else
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
}
}
}
int main()
{
scanf("%d",&n);
if(n==1){printf("0
");return 0;}
Euler();
for(int i=1;i<n;i++)
ans+=phi[i];
printf("%lld
",ans*2+1);
return 0;
}
P2568GCD
(Description)
求(1leq x,yleq n)且(GCD(x,y))为素数的((x,y)，1leq nleq 10^7)的对数。
(Solution)
求(1leq x,yleq n)且(GCD(x,y)=k)的对数也就是求(1leq x,yleq n/k)且(Gcd(x,y)=1)的对数。有了这个转换，就可以枚举素数。
问题就成了计算(sum_psum_{i=1}^{lfloorfrac{n}{p}
floor}sum_{j=1}^{lfloorfrac{n}{p}
floor}[gcd(i,j)=1])。利用上题的思路求解。
#include<complex>
#include<cstdio>
using namespace std;
const int N=1e7+7;
int n,tot;
int prime[N];
long long phi[N];
bool check[N];
void Init()
{
check[1]=phi[1]=1;
for(int i=2;i<=n;i++)
{
if(!check[i])prime[++tot]=i,phi[i]=i-1;
for(int j=1;j<=tot && i*prime[j]<=n;j++)
{
check[i*prime[j]]=1;
if(i%prime[j])phi[i*prime[j]]=phi[i]*phi[prime[j]];
else
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
}
}
for(int i=1;i<=n;i++)
phi[i]+=phi[i-1];
}
int main()
{
scanf("%d",&n);
Init();
long long ans=0;
for(int i=1;i<=tot;i++)
ans+=phi[n/prime[i]];
printf("%lld
",ans*2-tot);
return 0;
}
P1447 [NOI2010]能量采集
(Description)
求(sum_{i=1}^nsum_{j=1}^m2 imes(gcd(i,j)-1)+1,1leq n,mleq 10^5)
(Solution)
那么问题就在与求(sum_{i=1}^nsum_{j=1}^mgcd(i,j))（默认(n<m)），按照前两题的思路，容易想到枚举(gcd)，也就是求(sum_{r=1}^nrsum_{i=1}^nsum_{j=1}^m[gcd(i,j)=r])。
由于(i和j)的取值范围不同，不能像前两题一样用欧拉函数直接计算了，除非用莫比乌斯反演进行转换。但数据范围提示我们这题并不需要做到(O(n))。
考虑状态(f[r])表示(Gcd(i,j)=r)的((i,j))的对数。在(1leq xleq n,1leq yleq m)的范围中，(x和y)都是(r)的倍数的对数有(lfloorfrac{n}{r}
floor imeslfloorfrac{m}{r}
floor)，这其中还包含了(x,y)都是(r的2倍、3倍......)，所以(f[r]=lfloorfrac{n}{r}
floor imeslfloorfrac{m}{r}
floor-f[2r]-f[3r]-...)。
所以倒序枚举(r)求出(f[r])最后就可求出结果。总复杂度为(O(n/1)+O(n/2)+O(n/3)+...=O(nlogn))。虽然比莫比乌斯反演的做法多了一个(log)，但是实际代码跑起来还是略快于莫比乌斯反演。
#include<complex>
#include<cstdio>
using namespace std;
const int N=1e5+7;
int n,m;
long long f[N];
int main()
{
scanf("%d%d",&n,&m);
if(n>m)swap(n,m);
for(int i=n;i;i--)
{
f[i]=1ll*n/i*(m/i);
for(int j=i+i;j<=n;j+=i)
f[i]-=f[j];
}
long long ans=0;
for(int i=1;i<=n;i++)
ans+=1ll*i*f[i];
printf("%lld
",ans*2-1ll*n*m);
return 0;
}
P2303 [SDOI2012]Longge 的问题
(Description)
求(sum_{i=1}^ngcd(i,n),1leq nleq 2^{32})
(Solution)
按照套路枚举
可以将(n)质因数分解之后(dfs)枚举(n)的约数。也可以(O(sqrt n))枚举约数并(O(sqrt d))求出(phi(d))，但这种做法求(phi)相互独立，没有用到约数这一性质。由于第一种方法用到底贵，所以两种方法没有明显差别。
#include<complex>
#include<cstdio>
using namespace std;
const int N=37;
long long n,tot,ans;
long long prime[N],num[N];
void dfs(int x,long long now,long long phi)
{
if(x==tot)
{
ans+=n/now*phi;
return;
}
dfs(x+1,now,phi);
long long t=prime[x+1]-1;
for(int i=1;i<=num[x+1];i++,t*=prime[x+1])
dfs(x+1,now*=prime[x+1],phi*t);
}
int main()
{
scanf("%lld",&n);
long long tmp=n;
for(int i=2;1ll*i*i<=tmp;i++)
if(tmp%i==0)
{
prime[++tot]=i;
for(;tmp%i==0;tmp/=i)
num[tot]++;
}
if(tmp>1)prime[++tot]=tmp,num[tot]=1;
dfs(0,1,1);
printf("%lld
",ans);
return 0;
}
SP7001 VLATTICE - Visible Lattice Points
(Description)
(Tleq 50)组询问，每次给定一个(n imes n imes n,1leq nleq 10^6)的点阵，问从((0,0,0))能看到多少个不被遮挡的点（就是比仪仗队那题多了一维）。
(Solution)