洛谷P4388 付公主的矩形

首先有一个结论
对于一个$\left ( r,c \right ), \ gcd\left ( r,c \right )=1$的矩形，经过格子数目为$r+c-1$个
更一般的，可由上式化简，对于$\left ( r,c \right )$，经过格子数目为$r+c-gcd\left ( r,c \right )$

证明有多种
给出一种我当时想出来的

• $\left ( r,c \right )$中对角线只有初末位置在格点上
• 当对角线穿过某一网格边时，必然会在两边经过各一个格子
• 对角线穿过的网格边数显然为$r+c-2$
• 由于中间无格点，按照上述计算时中间每个格子会被计算到两次
• 初末位置的格子仅会被计算到一次
• 化简后可得格子数为$r+c-1$

暴力统计就能过了，复杂度比较玄学，大概是$O\left ( c*ans \right )$，$c$为一个不是很大常数（我猜的）

其实还有更有理有据的做法

$$\sum _{d\mid n}\sum \left [r+c=d+1,gcd\left ( r,c \right )=1 \right ]= \frac{\sum _{d\mid n}\varphi\left ( d+1 \right )+1}{2}$$

每一对$\left ( r,c \right )$都会被算到两次，但$\left ( n,n \right )$只会被算到一次
复杂度$O\left ( N \right )$

代码为暴力统计

#include<cstdio>
const int N=1e6+50;
int n,ans=0,idx=0,w[N];
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int main()
{
    scanf("%d",&n);
    for(int i=1;i*i<=n;i++)
        if (n%i==0)
        {
            w[++idx]=i;
            if (i*i!=n) w[++idx]=n/i;
        }
    for(int i=1;i<=idx;i++)
    {
        int sz=w[i]+1;
        for(int k=1;k<=sz/2;k++)
            if (gcd(k,sz-k)==1) ans++;
    }
    printf("%d\n",ans);
    return 0;
}