- 首页 > it技术 > >
Codeforces 235E Number Challenge (莫比乌斯反演)
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define inf 0x3f3f3f3f
#define N 4000020
#define M 1000020
#define LL long long
#define mod 1073741824
#define ls (i << 1)
#define rs (ls | 1)
#define md (ll + rr >> 1)
#define lson ll, md, ls
#define rson md + 1, rr, rs
#define B 350int p[N], cnt, s[N], d[N];
int mu[N], np[N];
int x[N];
void init() {
s[1] = 1, mu[1] = 1;
d[1] = 1;
for(int i = 2;
i < N;
++i) {
if(!np[i]) {
p[cnt++] = i;
mu[i] = -1;
d[i] = 2;
s[i] = i;
}
for(int j = 0;
j < cnt && i * p[j] < N;
++j) {
int t = i * p[j];
np[t] = 1;
if(i % p[j] == 0) {
mu[t] = 0;
s[t] = s[i] * p[j];
if(s[t] == t) d[t] = d[i] + 1;
else d[t] = d[t/s[t]] * d[s[t]];
break;
}
mu[t] = mu[i] * -1;
s[t] = p[j];
d[t] = d[i] * d[p[j]];
}
}
}int a, b, c;
int main() {
init();
LL ans = 0;
cin >> a >> b >> c;
for(int i = 1;
i <= a;
++i) {
for(int j = 1;
j <= b;
++j) {
x[i*j]++;
}
}
for(int i = 1;
i <= c;
++i) {
LL t1 = 0, t2 = 0;
for(int j = 1;
j <= c / i;
++j) {
t1 += d[j];
if(t1 >= mod) t1 -= mod;
}
for(int j = i;
j <= a * b;
j += i) {
t2 += 1LL * d[j/i] * x[j] % mod;
if(t2 >= mod) t2 -= mod;
}
ans += mu[i] * t1 % mod * t2 % mod;
ans %= mod;
if(ans < 0) ans += mod;
}
cout << ans << endl;
return 0;
}
推荐阅读
