「CF235E」Number Challenge

Source and Judge

CF235E

Record

2h

Analysis

请先思考后再展开

弟弟题:sdoi 约数个数和

一直在想怎么把约数个数联系到gcd上,结果原来是个结论: 约数与欧几里得 文章末尾第5条

$\sum \sum \sum d(n \cdot m \cdot k)$
$\sum \sum \sum \ \sum \sum \sum [gcd=1][gcd=1][gcd=1]$
直接枚举约数,降低复杂度
$$
\sum_x \sum_y \sum_z
\lfloor \frac{a}{x} \rfloor
\lfloor \frac{b}{y} \rfloor
\lfloor \frac{c}{z} \rfloor
[gcd(x,y)=1][gcd(x,z)=1][gcd(y,z)=1]
$$
然后,把mu的性质式子带入(看到等于1,可以考虑这样搞,是个套路)
$$
\sum_x \sum_y \sum_z
\lfloor \frac{a}{x} \rfloor
\lfloor \frac{b}{y} \rfloor
\lfloor \frac{c}{z} \rfloor
( \sum_{d|x,d|y} \mu(d) )[gcd(x,z)=1][gcd(y,z)=1]
$$
这样的好处是能通过枚举d找其倍数得到x和y(从根号变为log,尽管刚带入的时候感觉复杂度变大)
调整一下枚举顺序,第二个好处也凸显出来了,就是取消了x和y的关系,让其可以分开求和再乘起来
$$
\sum_d \mu(d) \times
\sum_z (\lfloor \frac{c}{z} \rfloor \times
(\Sigma_{d|x} [gcd(x,z)=1] \lfloor \frac{a}{x} \rfloor) \times
(\Sigma_{d|y} [gcd(y,z)=1] \lfloor \frac{b}{y} \rfloor))
$$
预处理gcd后,由调和级数可知复杂度为 $O(n^2logn)$
可见定理和mu的性质为本题最关键的两步

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
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#ifdef DEBUG
const int LOCAL=1;
#else
const int LOCAL=0;
#endif
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAX_N=2100;
int GCD(int x,int y)
{
if(y==0) return x;
return GCD(y,x%y);
}
int gcd[MAX_N][MAX_N];
bool no[MAX_N];
int pr=0,prime[MAX_N];
int mu[MAX_N];
void pre()
{
mu[1]=1;
for(int i=2;i<MAX_N;i++)
{
if(no[i]==0) prime[++pr]=i,mu[i]=-1;
for(int j=1;j<=pr and i*prime[j]<MAX_N;j++)
{
no[i*prime[j]]=1;
if(i%prime[j]==0) {mu[i*prime[j]]=0;break;}
mu[i*prime[j]]=-mu[i];
}
}
}
const int MOD=1<<30;
void main()
{
for(int i=1;i<MAX_N;i++) for(int j=1;j<MAX_N;j++) gcd[i][j]=GCD(i,j);
pre();
int a,b,c;scanf("%d%d%d",&a,&b,&c);
int ans=0;
for(int d=1;d<=a and d<=b;d++)
{
int tot=0;
for(int z=1;z<=c;z++)
{
int tot1=0,tot2=0;
for(int x=d;x<=a;x+=d) if(gcd[x][z]==1) tot1=(tot1+a/x)%MOD;
for(int y=d;y<=b;y+=d) if(gcd[y][z]==1) tot2=(tot2+b/y)%MOD;
tot=(tot+ll(c/z)*tot1%MOD*tot2%MOD)%MOD;
}
ans=ans+tot*mu[d];//debug 减法……
ans=(ans%MOD+MOD)%MOD;
}
printf("%d",ans);
}
};
int main()
{
srand(time(0));
mine::main();
}

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