ACM|Codeforces 235E Number Challenge (神定理＋莫比乌斯反演) 数论|组合数学

【ACM|Codeforces 235E Number Challenge (神定理＋莫比乌斯反演)】

E. Number Challenge time limit per test：3 seconds
memory limit per test：512 megabytes

Let's denote d(n) as the number of divisors of a positive integern. You are given three integers a, b and c. Your task is to calculate the following sum:

文章图片
Find the sum modulo 1073741824(230).
Input The first line contains three space-separated integersa, b andc (1?≤?a,?b,?c?≤?2000).
Output Print a single integer — the required sum modulo1073741824 (230).
Sample test(s) Input

2 2 2

Output

20

Input

4 4 4

Output

328

Input

10 10 10

Output

11536

Note For the first example.

d(1·1·1)?=?d(1)?=?1;
d(1·1·2)?=?d(2)?=?2;
d(1·2·1)?=?d(2)?=?2;
d(1·2·2)?=?d(4)?=?3;
d(2·1·1)?=?d(2)?=?2;
d(2·1·2)?=?d(4)?=?3;
d(2·2·1)?=?d(4)?=?3;
d(2·2·2)?=?d(8)?=?4.

So the result is 1?+?2?+?2?+?3?+?2?+?3?+?3?+?4?=?20.

题目链接：http://codeforces.com/contest/235/problem/E

题目大意：就是算那个公式的值

题目分析：第一次写DIV1的E，还是CLJ出的题，直接给出rng_58给的一个公式吧:

文章图片

知道这个公式以后基本就可以秒掉这题了，先枚举i的因子，然后在gcd(i, j) = gcd(i, k) = 1的条件下，为了让gcd(j, k) = 1，直接对b,c进行莫比乌斯反演，跑出来2000ms+，这里有个优化，考虑到a，b，c的范围不是很大，可以对gcd记忆化，瞬间变成500ms+

#include #include #define ll long long using namespace std; int const MAX = 2005; int const MOD = 1 << 30; int gd[MAX][MAX], mob[MAX], p[MAX]; bool noprime[MAX]; void Mobius() { int pnum = 0; mob[1] = 1; for(int i = 2; i < MAX; i++) { if(!noprime[i]) { p[pnum ++] = i; mob[i] = -1; } for(int j = 0; j < pnum && i * p[j] < MAX; j++) { noprime[i * p[j]] = true; if(i % p[j] == 0) { mob[i * p[j]] = 0; break; } mob[i * p[j]] = -mob[i]; } } }int Gcd(int a, int b) { if(b == 0) return a; if(gd[a][b]) return gd[a][b]; return gd[a][b] = Gcd(b, a % b); }ll cal(int d, int x) { ll ans = 0; for(int i = 1; i <= d; i++) if(Gcd(i, x) == 1) ans += (ll) (d / i); return ans; }int main() { Mobius(); int a, b, c; ll ans = 0; scanf("%d %d %d", &a, &b, &c); for(int i = 1; i <= a; i++) for(int j = 1; j <= min(b, c); j++) if(Gcd(i, j) == 1) ans = (ans % MOD + (ll) (a / i) * mob[j] * cal(b / j, i) * cal(c / j, i) % MOD) % MOD; printf("%I64d\n", ans); }