题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3435
题意: 给出一个三维坐标 (x, y, z), 问该点与 (1, 1, 1) 组成的长方体中有多少条经过点 (1, 1, 1) 的直线 .
思路: 显然本题的难点是线段不能重复计算, 比如 (1, 1, 1) 到 (2, 2, 2) 和 (1, 1, 1) 到 (4, 4, 4) 同一条直线 .
为了计算方便, 我们先将这个问题替换成它的等价问题: 求 (0, 0, 0), (x - 1, y - 1 , z - 1) 组成的长方体中有多少条经过 (0, 0, 0) 的直线 .
通过画图可以发现当且仅当点 (j, k, l) 满足 gcd(j, k, l) = 1 时累计直线 (0, 0, 0), (j, k, l) 刚好能累加到所有直线并且不会重复计算 .
然后我们将满足条件的直线分为 3 部分:
1. 从 (0, 0, 0) 出发的 3 条棱；
2. 从 (0, 0, 0) 出发的 3 个表面；
3. 从 (0, 0, 0) 出发到长方体内部的直线；
对于 1, 显然满足条件的直线为 3 条；
对于 2, 满足条件的直线数目为 gcd(j, k) = 1 的直线数目加 gcd(j, l) = 1 的直线数目加 gcd(k, l) = 1 的直线数目, 其中 1 <= j <= x -1, 1 <= k <= y - 1, 1 <= l <= z -1；
对于 3, 满足条件的直线数目为 gcd(j, k, l) = 1 的直线数目, 其中 1 <= j <= x -1, 1 <= k <= y - 1, 1 <= l <= z -1；
显然对于上面的计算部分都可以用莫比乌斯反演在线性时间内完成 .
代码:
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #define ll long long 5 using namespace std; 6 7 const int MAXN = 1e6 + 10; 8 9 bool check[MAXN]; 10 int prime[MAXN], mu[MAXN], sum[MAXN]; 11 12 void Moblus(void){ 13 memset(check, false, sizeof(check)); 14 int tot = 0; 15 mu[1] = 1; 16 sum[1] = 1; 17 for(int i = 2; i < MAXN; i++){ 18 if(!check[i]){ 19 prime[tot++] = i; 20 mu[i] = -1; 21 } 22 for(int j = 0; j < tot && prime[j] * i < MAXN; j++){ 23 check[prime[j] * i] = true; 24 if(i % prime[j] == 0){ 25 mu[i * prime[j]] = 0; 26 break; 27 }else mu[i * prime[j]] = -mu[i]; 28 } 29 sum[i] = sum[i - 1] + mu[i]; 30 } 31 } 32 33 ll solve(int x, int y){ 34 ll ans = 0; 35 if(x > y) swap(x, y); 36 for(int i = 1, la = 0; i <= x; i = la + 1){ 37 la = min(x / (x / i), y / (y / i)); 38 ans += (ll)(sum[la] - sum[i - 1]) * (x / i) * (y / i); 39 } 40 return ans; 41 } 42 43 ll solve(int x, int y, int z){ 44 ll ans = 0; 45 if(x > y) swap(x, y); 46 if(x > z) swap(x, z); 47 for(int i = 1, la = 0; i <= x; i = la + 1){ 48 la = min(min(x / (x / i), y / (y / i)), z / (z / i)); 49 ans += (ll)(sum[la] - sum[i - 1]) * (x / i) * (y / i) * (z / i); 50 } 51 return ans; 52 } 53 54 int main(void){ 55 Moblus(); 56 int x, y, z; 57 while(~scanf("%d%d%d", &x, &y, &z)){ 58 x--; 59 y--; 60 z--; 61 ll ans = 3; 62 ans += solve(x, y); 63 ans += solve(x, z); 64 ans += solve(y, z); 65 ans += solve(x, y, z); 66 printf("%lld ", ans); 67 } 68 return 0; 69 }