GCD HDU - 1695 莫比乌斯反演入门

题目链接:https://cn.vjudge.net/problem/HDU-1695#author=541607120101

感觉讲的很好的一个博客:https://www.cnblogs.com/peng-ym/p/8647856.html

今天刚开始学莫比乌斯反演,先据我所了解的说一下。

首先是莫比乌斯函数

1,mu(x).当x为1时,mu(1)等于1。

2,当x为素数时,mu(x)=-1。

3,当x能唯一分解成多个不同的素数相乘的时候(不能有重复的素数)mu(x)=(-1)的k次方,k代表的是素数的个数。

4,当x不能被唯一的分解成多个素数相乘的时候,也就是他的因子中存在重复的素数,这个时候,mu(x)=0.

然后是一个等式GCD HDU - 1695   莫比乌斯反演入门 (d是n的因子).

然后就是两个等式(等我学会证明就回来补~)

GCD HDU - 1695   莫比乌斯反演入门

然后对于当前这个题,选择(1,b),(1,d) 中满足gcd(x,y)==k的对数,(1<=x<=b),(1<=y<=d) .

也就是说 gcd(x/k,y.k)==1满足的对数.

然后再开始分析一波:

我们令f(k)为满足(a,b),(c,d)中的gcd为k的对数.然后F(k)就是满足(a,b),(c,d)中的gcd为k的倍数的对数.

F(k)就等于(b/k)*(d/k).

所以说,这个题就转换为了求满足GCD HDU - 1695   莫比乌斯反演入门的总和

但是要注意去重.我们一开始定义的是ans=f(1)( (1<=x<=b) &&(1<=y<=c) )中的解,但是很明显,(1.c)包含(1,b),所以这一块会有重复的计算( (1<=x<=b)&&(1<=x<=b) ),并且(t1,t2)和(t2,t1)在(1,b)这块区域,是应当被看做一组的,所以最终结果应该是

ans=f ( (1,b) , (1,c) )-f ( (1,b) , (1,b) ) / 2.

AC代码:

#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
#include<cstring>
#include<stdio.h>
using namespace std;
# define ll long long
# define inf 0x3f3f3f3f
const int maxn =100000+100;
# define ll long long
ll mu[maxn];
ll vis[maxn];
ll prim[maxn];
void Get_mu(ll n)
{
mu[1]=1;
int cnt=0;
for(ll i=2; i<n; i++)
{
if(!vis[i])
{
prim[cnt++]=i;
mu[i]=-1;
}
for(ll j=0; j<cnt; j++)
{
ll k=i*prim[j];
if(k>n)break;
vis[k]=1;
if(i%prim[j])
{
mu[k]=-mu[i];
}
else
{
mu[k]=0;
break;
}
}
}
}
int main()
{
Get_mu(maxn);
ll t;
ll Case=0;
scanf("%lld",&t);
while(t--)
{
ll a,b,c,d,k;
scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&k);
if(k==0)
{
printf("Case %lld: 0\n",++Case);
continue;
}
b/=k;
d/=k;
ll ans=0,res=0;
ll minn=min(b,d);
for(ll i=1; i<=minn; i++)
{
ans+=mu[i]*(b/i)*(d/i);
res+=mu[i]*(minn/i)*(minn/i);
}
// cout<<ans<<" "<<res<<endl;
printf("Case %lld: %lld\n",++Case,ans-res/2);
}
return 0;
}
上一篇:图片生成操作属性导致WP内存溢出解决办法


下一篇:Atitit orm的实现模式 data-mapper模式和active-record模式有什么区别