【Zoj3435】Ideal Puzzle Bobble

来源和评测点

Author: ZHU, Yuke
Contest: ZOJ Monthly, November 2010
Zoj3435
Caioj1283

题目

【题目大意】
给定点(x,y,z)与(1,1,1)确定一个长方体,长方体边上及内部总共有xyz个点,问从(1,1,1)总共能看到多少个点
【输入格式】
多组数据
一行三个整数,x,y,z
1<=a,b,c<=1000000
【输出格式】
共1行,一个整数从(1,1,1)总共能看到多少个点
【输入样例】
2 2 2
3 3 3
【输出样例】
7
19

分析

莫比乌斯反演教程和题目分类参见:
【OI之路】11更高级数论-2莫比乌斯反演
其他莫比乌斯反演题目参见:Tag-莫比乌斯反演

建议先看二维版:仪仗队

用了分块
讲(x,y,z)与(1,1,1)变成(x-1,y-1,z-1)与(0,0,0)
三个数的gcd是一样的,注意0
答案就是:(都不是0)+(一个0)+(两个0也就是3)分别反演结果之和

代码

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int mymin(int x,int y) {return x<y?x:y;}
typedef long long ll;
//******************定义******************
const int MAXNUM=1000000,MAXPR=100000;
int mu[MAXNUM+10];
//******************莫比乌斯函数******************
int prime[MAXPR+10],pr;
bool prv[MAXNUM+10];
void getmu()
{
pr=0;memset(prv,1,sizeof(prv));
mu[1]=1;
for(int i=2;i<=MAXNUM;i++)
{
if(prv[i]==1)
{
prime[++pr]=i;
mu[i]=-1;
}
for(int j=1;j<=pr;j++)
{
int t=i*prime[j];
if(t>MAXNUM) break;
prv[t]=0;
if(i%prime[j]==0)
{
mu[t]=0;
break;
}
else mu[t]=-mu[i];
}
mu[i]+=mu[i-1];
}
}
//******************莫比乌斯反演******************
ll calc1(int a,int b,int c)
{
//已经不必强调大小了,找到最小值就好了
//其实也就模板题需要去重所以才要交换罢了
int mi=mymin(a,mymin(b,c));
ll ans=0;
int last;
int t=1;
for(int i=1;i<=mi;i=last+1)//d/t
{
int d=i*t;
last=mymin( a/(a/d), mymin( b/(b/d),c/(c/d) ) );
ans+=ll(mu[last]-mu[i-1])*( ll(a/d)*ll(b/d)*ll(c/d) );
}
return ans;
}
ll calc2(int a,int b)
{
int mi=mymin(a,b);
ll ans=0;
int last;
int t=1;
for(int i=1;i<=mi;i=last+1)//d/t
{
int d=i*t;
last=mymin( a/(a/d),b/(b/d) );
ans+=ll(mu[last]-mu[i-1])*( ll(a/d)*ll(b/d) );
}
return ans;
}
//******************主函数******************
int main()
{
getmu();
int x,y,z;
while(scanf("%d%d%d",&x,&y,&z)!=EOF)
{
//都不是0+一个0+两个0
printf("%lld\n",calc1(x-1,y-1,z-1)+calc2(x-1,y-1)+calc2(y-1,z-1)+calc2(x-1,z-1)+3);
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2017-11/Ideal_Puzzle_Bobble.html
转载请注明出处,谢谢!

给我投食吧,您的支持将鼓励我继续创作!