2012-0005

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

zhan by yxdb
{{{
#include <cstdio>

typedef unsigned long long ull;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

ull C(int n, int a) {
    if (n < a) return 0ULL;
    ull ret = 1ULL;
    for (int i = 0; i < a; ++i) {
        ret *= n-i;
        ret /= i+1;
    }
    return ret;
}

int main() {
    int n, m;
    while (2==scanf("%d%d",&n,&m)) {
        ull ans = C((n+1)*(m+1), 3) - (m+1)*C(n+1,3) - (n+1)*C(m+1,3);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                int k = gcd(i, j);
                ans -= 2ULL*(k-1)*(n-i+1)*(m-j+1);
            }
        }
        printf("%llu\n", ans);
    }
}
}}}

zhan by yxdb

#include <cstdio>
typedef unsigned long long ull;
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
ull C(int n, int a) {
    if (n < a) return 0ULL;
    ull ret = 1ULL;
    for (int i = 0; i < a; ++i) {
        ret *= n-i;
        ret /= i+1;
    }
    return ret;
}
int main() {
    int n, m;
    while (2==scanf("%d%d",&n,&m)) {
        ull ans = C((n+1)*(m+1), 3) - (m+1)*C(n+1,3) - (n+1)*C(m+1,3);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                int k = gcd(i, j);
                ans -= 2ULL*(k-1)*(n-i+1)*(m-j+1);
            }
        }
        printf("%llu\n", ans);
    }
}