题目链接：
Codeforces 235 E Number Challenge
题意:
记d(i)表示i的约数个数，计算：∑i=1a∑j=1b∑k=1cd(ijk)，a,b,c∈[1,2000]
分析：
Ans = ∑i=1a∑j=1b∑k=1cd(ijk) = ∑i=1a?ai?∑j=1b?bj?∑k=1c?ck?gcd(i,j)=gcd(i,k)=gcd(j,k)=1
对于后面的部分反演可得： Ans=∑i=1i=a?ai?∑dmin(b,c)μ(d)∑d|j,(i,j)=1?bj?∑d|k,(i,k)=1?ck?
记j=dj',k=dk',则：记j=dj',k=dk',则：
Ans=∑i=1i=a?ai?∑dmin(b,c)μ(d)∑gcd(i,dj′)=1?bdj′?∑gcd(i,dk′)=1?cdk′?
,
因为 gcd(i,dj′)=1，我们先保证 gcd(i,d)=1,然后枚举 j′:1→bd,保证 gcd(i,j′)=1，这样就可以使得 gcd(i,dj′)=1，累加即可。对于 gcd(i,dk′)=1同样处理。
枚举 i和 d的时间复杂度是是 a和 min(b,c),但是枚举 j′和k′的时间复杂度是 ∑i=bi=1b/i和 ∑i=ci=1c/i,所以总的时间复杂度大概是 O(a?b?log(b))【莫比乌斯反演|Codeforces 235 E Number Challenge(莫比乌斯反演)】
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int MAX_N = 2010;
const ll mod = (ll)1 << 30;
int prime_cnt, prime[MAX_N], mu[MAX_N], gcd[MAX_N][MAX_N];
bitset bs;
void GetMu()
{
prime_cnt = 0;
bs.set();
mu[1] = 1;
for(int i = 2;
i < MAX_N;
++i) {
if(bs[i]) {
prime[prime_cnt++] = i;
mu[i] = -1;
}
for(int j = 0;
j < prime_cnt && i * prime[j] < MAX_N;
++j) {
bs[i * prime[j]] = 0;
if(i % prime[j]) {
mu[ i * prime[j]] = - mu[i];
}else {
mu[i * prime[j]] = 0;
break;
}
}
}
}inline int GCD(int a, int b)
{
if(gcd[a][b]) return gcd[a][b];
else return b == 0 ? a : gcd[a][b] = GCD(b, a % b);
}inline void GetGcd()
{
for(int i = 1;
i < MAX_N;
i++){
for(int j = i;
j < MAX_N;
j++) {
gcd[i][j] = gcd[j][i] = GCD(i, j);
}
}
}inline ll work(int n, int x)
{
ll res = 0;
for(int i = 1;
i <= n;
++i) {
if(gcd[i][x] == 1) {
res = (res + (n / i)) % mod;
}
}
return res;
}inline ll solve(int a, int b, int c)
{
ll res = 0;
int top = min(b, c);
for(int i = 1;
i <= a;
++i) {
for(int d = 1;
d <= top;
++d){
if(gcd[i][d] == 1) {
ll tmp = 0;
tmp = (ll) (a / i) * mu[d] * work(b / d, i) % mod * work(c / d, i) % mod;
res = ((res + tmp) % mod + mod) % mod;
}
}
}
return res;
}int main()
{
GetMu();
GetGcd();
int a, b, c;
while(~scanf("%d%d%d", &a, &b, &c)) {
printf("%lld\n", solve(a, b, c));
}
return 0;
} 推荐阅读
- codeforces B. Young Explorers
- codeforces C. Mere Array
- codeforces D. Omkar and Bed Wars
- codeforces C. Omkar and Waterslide
- codeforces B. Omkar and Infinity Clock
- codeforces B. Ternary Sequence
- 题库-CF|【Codeforces Round 370 (Div 2) E】【线段树 等比数列 区间合并】Memory and Casinos 赌场区间[l,r] l进r先出的概率
- 题库-CF|【Codeforces Round 263 (Div 2)C】【贪心 哈弗曼思维】Appleman and Toastman 每个非1size子树延展为2子树的最大权
- Codeforces|Codeforces Round #605 (Div. 3) D. Remove One Element
- Codeforces|Codeforces Round #643 (Div. 2) B.Young Explorers