给定一个nm的矩阵，定义矩阵第i行第j列的值为gcd(i,j) (gcd为最大公因数) 定义子矩阵的和是其中所有元素之和 ，现在需要求所有kk的子矩阵的和的总和 1<=n,m<=5e3 1<=k<=min(n,m)用c语言写

以下是使用C语言实现的代码：

#include <stdio.h>

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a%b);
}

int main()
{
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);

    // 计算前缀和数组
    long long prefix_sum[n+1][m+1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int g = gcd(i, j);
            prefix_sum[i][j] = prefix_sum[i-1][j] + prefix_sum[i][j-1] - prefix_sum[i-1][j-1] + g;
        }
    }

    // 计算所有kk子矩阵的和的总和
    long long ans = 0;
    for (int i = 1; i <= n-k+1; i++) {
        for (int j = 1; j <= m-k+1; j++) {
            ans += prefix_sum[i+k-1][j+k-1] - prefix_sum[i+k-1][j-1] - prefix_sum[i-1][j+k-1] + prefix_sum[i-1][j-1];
        }
    }

    printf("%lld\n", ans);
    return 0;
}

我们首先定义了一个gcd函数来计算最大公因数。然后，我们读入矩阵的大小n和m以及子矩阵的大小k。接着，我们使用一个二维数组prefix_sum来存储前缀和，其中prefix_sum[i][j]表示以第1行第1列为左上角，第i行第j列为右下角的子矩阵的和。我们使用两个for循环遍历矩阵中的每个元素，计算其gcd值并将其加入到prefix_sum数组中。

接下来，我们使用另外两个for循环遍历所有kk子矩阵，并使用前缀和数组计算其和，并将其加入到总和ans中。最后，我们输出ans即可得到最终答案。

注意，由于矩阵中的元素可能非常大，因此需要使用long long类型来保存前缀和和答案。