题目链接
HDU1695
思路
题目要求的是下面这个式子
转化一下变成
然后就可以用莫比乌斯反演来求了
设f(n)为gcd(a,b)=n的个数
则F(n)为gcd(a,b)=n及n的倍数的个数
则有
然后用莫比乌斯倍数反演得到
然后f(1)就是我们要求的答案，显而易见
F(t)=(N/t)*(M/t);
最后
我们可以计算莫比乌斯函数的前缀和，用分块除法加速右边的式子。
然后减去重复的个数，我们分为两部分，一部分为ans1=(N,N),另一部分为ans2=(N,M),这里N<M。
那么重复只会出现在前面一部分所以除以2就是重复的数值。答案就等于ans2-ans1/2;
思路二
基本上反演的套路和上面一样得到
这里我们直接考虑F(n)怎么求，F(n)如果计算重复的话就是
我们需要减去重复的，就取他们的交集，把相同的个数减去除以2即可
此处
m=min(b,d);
k=max(a,c);
交集为(k,m)，需要判断交集不存在，不存在则返回上面的F(n),否则为
代码实现
方法1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5+10;
int mu[maxn];
bool vis[maxn];
int sum[maxn];
int prime[maxn],cnt;
void get_mu()
{
mu[1]=1;
for(int i=2;i<maxn;i++)
{
if(!vis[i])
{
mu[i]=-1;
prime[cnt++]=i;
}
for(int j=0;j<cnt&&prime[j]*i<maxn;j++)
{
vis[i*prime[j]]=true;
if(i%prime[j])
{
mu[i*prime[j]]=-mu[i];
}
else
{
mu[i*prime[j]]=0;
break;
}
}
}
sum[0]=0;
for(int i=1;i<maxn;i++)sum[i]=mu[i]+sum[i-1];
}
int main()
{
int T;
scanf("%d",&T);
get_mu();
for(int cas=1;cas<=T;cas++)
{
int a,b,c,d,k;
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
printf("Case %d: ",cas);
if(k==0)
{
printf("0\n");
continue;
}
b/=k;
d/=k;
if(b>d)swap(b,d);
ll ans1 = 0;
int last;
for(int i=1;i<=b;i=last+1)
{
last=min(b/(b/i),d/(d/i));
ans1+=1ll*(sum[last]-sum[i-1])*(b/i)*(d/i);
}
long long ans2 = 0;
for(int i=1;i<=b;i=last+1)
{
last=b/(b/i);
ans2+=1ll*(sum[last]-sum[i-1])*(b/i)*(b/i);
}
long long ans = ans1-ans2/2;
printf("%lld\n",ans);
}
}
|
方法二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+10;
int prime[N],mu[N],cnt;
bool vis[N];
void init()
{
vis[1]=true;
mu[1]=1;
for(int i=2;i<N;i++)
{
if(!vis[i])
{
prime[cnt++]=i;
mu[i]=-1;
}
for(int j=0;j<cnt&&i*prime[j]<N;j++)
{
vis[i*prime[j]]=true;
if(i%prime[j])mu[i*prime[j]]=-mu[i];
else
{
mu[i*prime[j]]=0;
break;
}
}
}
}
long long a,b,c,d,n;
ll getF(int x)
{
long long m = min(b,d);
long long k = max(a,c);
if(m<=k)return 1ll*(b/x-(a-1)/x)*(d/x-(c-1)/x);
return 1ll*(b/x-(a-1)/x)*(d/x-(c-1)/x)-1ll*(((m-k+1)/x)*((m-k+1)/x)-(m-k+1)/x)/2;
}
int main()
{
int t;
scanf("%d",&t);
init();
for(int cas=1;cas<=t;cas++)
{
cin>>a>>b>>c>>d>>n;
ll ans = 0;
ll limit = min(b,d);
if(n==0)
{
cout<<"Case "<<cas<<": 0"<<endl;
continue;
}
for(int i=n,j=1;i<=limit;i+=n,j++)
{
ans+=1ll*mu[j]*getF(i);
}
cout<<"Case "<<cas<<": ";
cout<<ans<<endl;
}
}
|