hdu1695 GCD
题目描述
给出 a,b,c,d,e (a=1,c=1)
求
\sum_{i=1}^b\sum_{j=1}^d[\gcd(i,j)=e]
令 n=\lfloor \frac{b}{e}\rfloor ,m=\lfloor \frac{d}{e}\rfloor ,
即求
\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1]
考虑令 f(d)=\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]
那么F(x)=\sum\limits{x|d}f(d)
F(d) 表示有多少 (i,j) ,1\leq i\leq n , 1\leq j \leq m 满足 gcd(i,j)=d 的倍数
显然有 F(d)= \lfloor\frac{n}{d}\rfloor\times \lfloor \frac{m}{d} \rfloor
根据莫比乌斯反演,有
f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d)
求出 f(1) 即可。
因为将 (x,y) 与 (y,x) 看成了同一数对,所以我们不妨设刚才求出的答案为 a(b,d)
题目所求答案为 :a(b,d)-a(b,b)/2
只求建箭头方向从左指向右的贡献
#include<bits/stdc++.h>
const int maxn = 1e5+10;
bool vis[maxn];
int prime[maxn];
int Mob[maxn];
int g[maxn];
void Mobius_sieve(){
int cnt = 0;
vis[1] = 1;
Mob[1] = 1;
for(int i = 2; i < maxn; i++){
if(!vis[i])
prime[cnt++] = i, Mob[i] = - 1 , g[i] = 1;
for(int j = 0; j < cnt && 1LL * prime[j] * i < maxn; j++){
vis[prime[j] * i] = 1;
g[prime[j]*i] = g[i] + 1;
Mob[i * prime[j]] = (i % prime[j] ? -Mob[i]: 0);
if(i % prime[j] == 0)
break;
}
}
}
int main(){
Mobius_sieve();
int k=0,t,a,b,c,d,e;
scanf("%d",&t);
while(t--){
scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
if(e==0){
printf("Case %d: %lld\n",++k,0ll);
continue;
}
c=b,d=d;
long long f_1 = 0 ,_f_1 = 0 ;
if(c>d) std::swap(c,d);
for(int i=e;i<=c;i+=e){
f_1+= Mob[i/e] * (1ll*(c/i)*(d/i));
}
for(int i=e;i<=c;i+=e){
_f_1+= Mob[i/e] * (1ll*(c/i)*(c/i));
}
printf("Case %d: %lld\n",++k,f_1-_f_1/2);
}
return 0;
}
0 条评论