题解：P4388 付公主的矩形

mahaorui2012 · 2025-01-31 10:09:00 · 题解

思路

首先，对于一个长为 R，宽度为 C 的长方形，其对角线所穿过的格子数量为 R+C-\gcd (R,C)，证明如下：

证明

不妨将对角线所穿过的格子数量转化为一从左上角运动到右下角的点的所穿过的格子数量，两者一定相等。

这个点应共横向移动 R 个单位，竖向移动 C 个单位，在该点不经过格点的情况下，共会经过 (R-1)+(C-1)=R+C-2 条边。

又该点每经过一个边，其经过的格子数量就会增加 1，左上角的格子不需经过边也一定可达，这个点会经过 R+C-2+1=R+C-1 个格点。

最后，在该点经过非左上角或右下角格点时，此时只经过了一条边（两条边重叠在了一起），但被计算了两次。又由下述引理可知，该点共经过 \gcd (R,C)-1 个非左上角或右下角格点，即共经过 (R+C-1)-(\gcd (R,C)-1)=R+C-\gcd (R,C) 个格子。

引理证明

首先，当 \gcd (R,C)=1 时，非左上角或右下角格点（以下称“格点”）个数为 0，因为若该值不为 0，则一定可以将该长方形分为若干个小长方形，使其长宽之最大公因数为 1。又可以这样做任意多次，总经过格点数必将趋近于正无穷，而 R 与 C 均有限，该长方形内的格点数量必将有限，与前假设矛盾。

则此时对角线经过了 0+1=1 个非左上角格点，该点为其右下角。

对于 \gcd (R,C)\parallel 1 的情况，一定可以将其分为 \gcd(R,C) 个小长方形，使其边长最大公因数为 1，即对角线共会经过 \gcd (R,C) 个非左上角格点（小长方形右下角点两两不重），即共经过 \gcd (R,C) 个非左上角格点，\gcd (R,C)-1 个格点。

又 1-1=0，\gcd (R,C)=1 也可并入到该情况里。

此时可得原题相当于关于 R 和 C 的方程 N=R+C-\gcd (R,C) 的解的组数。

化简方程

设 g=\gcd (R,C)，则设 R=pg，C=qg，由最大公因数定义可知 \gcd (p,q)=1，有：

易知该方程解的组数与原方程解的组数相等。

又 g,p,q,1\in \mathbb{N}，N 必为 g 的倍数，即 g 为 N 的因数。

可以枚举 g 和 p，有：

此时用上公式计算出 q，再判断 \gcd (p,q) 是否为 1 即可。

AC CODE

#include <iostream>
#include <algorithm>
using namespace std;

int n;

int calc(const int& i){
    int ret=0;
    for(int p=1;p<=n/i+1-p;++p){
        if(__gcd(p,n/i+1-p)==1){
            ++ret;
        }
    }
    return ret;
}

int main(){
    cin>>n;
    long long ans=0;
    for(int i=1;i*i<=n;++i){
        if(!(n%i)){
            ans+=calc(i);
            if(i*i!=n){
                ans+=calc(n/i);
            }
        }
    }cout<<ans;
    return 0;
}