首页 > 代码库 > uva 10542 - Hyper-drive(容斥)
uva 10542 - Hyper-drive(容斥)
题目链接:uva 10542 - Hyper-drive
题目大意:给定n维空间的线段,问说线段经过几个格子。
解题思路:对于线段可以将一点移动至原点,变成
(0,0)到(a,b)这条线段,以二维为例,每次会从一个格子移动到另一个格子,可以是x+1坐标,也可以是y+1,所以总的应该是a+b-1,扣除掉x+1,y+1的情况gcd(a,b)-1 (原点)。映射成n维就要用容斥原理计算结果。
/***********************
* (0, 0, 0, ...) -> (a, b, c, ...)
* ans = a + b + c +.. - gcd(a,b) - gcd(a,c) - .. + gcd(a, b, c) ...
***********************/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 15;
int N, d[maxn], g[2][maxn];
inline int gcd (int a, int b) {
return b == 0 ? a : gcd (b, a%b);
}
void init () {
scanf("%d", &N);
for (int i = 0; i < 2; i++)
for (int j = 0; j < N; j++)
scanf("%d", &g[i][j]);
for (int i = 0; i < N; i++)
d[i] = abs(g[0][i] - g[1][i]);
}
ll solve () {
ll ans = 0;
for (int i = 1; i < (1<<N); i++) {
int sign = -1, tmp = -1;
for (int j = 0; j < N; j++) {
if (i&(1<<j)) {
tmp = (tmp == -1 ? d[j] : gcd(tmp, d[j]));
sign *= -1;
}
}
ans += tmp * sign;
}
return ans;
}
int main () {
int cas;
scanf("%d", &cas);
for (int i = 1; i <= cas; i++) {
init();
printf("Case %d: %lld\n", i, solve());
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。