【HDOJ】4983 Goffi and GCD

题意说的非常清楚，即求满足gcd(n-a, n)*gcd(n-b, n) = n^k的(a, b)的不同对数。显然gcd(n-a, n)<=n, gcd(n-b, n)<=n。因此当n不为1时，当k>2时，不存在满足条件的(a,b)。而当k=2时，仅存在(n, n)满足条件。因此仅剩n=1以及k=1需要单独讨论：
当n = 1时，无论k为何值，均有且仅有(1,1)满足条件，此时结果为1；
当k = 1时，即gcd(n-a, n)*gcd(n-b, n) = n，则令gcd(n-a, n) = i，则gcd(n-b, n) = n/i。也即求(n-a)/i与n/i互素且(n-b)/(n/i)与n/(n/i)互素的(a, b)的对数和。

#include <cstdio>
#include <cmath>

const int MOD = (1e9+7);

__int64 getNotDiv(int x) {
    int i, r = x;
    __int64 ret = x;

    for (i=2; i*i<=r; ++i) {
        if (x%i == 0) {
            ret -= ret/i;
            while (x%i == 0)
                x /= i;
        }
    }
    if (x > 1)
        ret -= ret/x;
    return ret;
}

int main() {
    int n, k;
    int i, j;
    __int64 ans, tmp;

    while (scanf("%d %d", &n, &k) != EOF) {
        if (n==1 || k==2)
            printf("1\n");
        else if (k==1) {
            ans = 0;
            for (i=1; i*i<=n; ++i) {
                if (n%i == 0) {
                    j = n/i;
                    tmp = getNotDiv(i)*getNotDiv(j)%MOD;
                    if (j == i) {
                        ans += tmp;
                    } else {
                        ans += tmp<<1;
                    }
                    ans %= MOD;
                }
            }
            printf("%I64d\n", ans%MOD);
        } else {
            printf("0\n");
        }
    }

    return 0;
}