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 
#include 
#include 
#include 
#include 

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<