Luogu 4388 付公主的矩形

还是挺妙的。

发现对于一个$r$行$c$列的矩阵，穿过的格子数$n = r + c - gcd(r, c)$，题目中其实给定了这个$n$，要我们计算满足这个式子的$r$和$c$的个数。

发现$n$一定要是$gcd(r, c)$的倍数，等式两边可以除掉这个$gcd(r, c)$，变成$n' = r' + c' - 1$。

那么这时候$gcd(r', c') = gcd(n' + 1 - r', c') = 1$。

根据辗转相减法，有$gcd(n' + 1, c') = 1$，而满足这个式子的$c'$的个数恰好是$\varphi (n' + 1)$。

于是可以开心地计算出$c'$的总数$sum = \sum_{d|n} \varphi (d + 1)$。

注意到这时$(n, n)$这一对数只算了一遍，所以最后的答案$ans = (sum + 1) / 2$。

线性筛一波就好啦，时间复杂度$O(n)$。

Code：

#include <cstdio>

#include <cstring>

using namespace std;

const int N = 1e6 + ;

int n, pCnt = , ans = , pri[N], phi[N];

bool np[N];

inline void sieve() {

    phi[] = ;

    for(int i = ; i <= n + ; i++) {

        if(!np[i]) pri[++pCnt] = i, phi[i] = i - ;

        for(int j = ; j <= pCnt && i * pri[j] <= n + ; j++) {

            np[i * pri[j]] = ;

            if(i % pri[j] == ) {

                phi[i * pri[j]] = phi[i] * pri[j];

                break;

            }

            phi[i * pri[j]] = phi[i] * phi[pri[j]];

        }

    }

}

int main() {

    scanf("%d", &n);

    sieve();

    for(int i = ; i <= n; i++)

        if(n % i == ) ans += phi[i + ];

    printf("%d\n", (ans + ) / );

    return ;

}