P4388 付公主的矩形 题解

发布于 2020-08-18  687 次阅读


题意

题目链接

题目中给出了一个 $N$ ,而我们要求的是有多少对$(a,b)$ 使得一个 $a$ 行 $b$ 列的矩形,满足其对角线穿过的格子数为 $N$。

解析

通过画图以及对题意的观察与分析,我们发现,对于一个 $a,b$ 互质的矩形,其对角线穿过的格子应该是呈阶梯状上升的(如图)。

我们再像小学做这类数学题一样,将这些格子推向两边,可以数出穿过的格子数就为 $a+b-1$。

而对于一个 $a,b$ 不互质的矩形,显然可以将其拆分为 $\gcd{(a,b)}$ 个互质的矩形,如图。

也就是说,我们只需要先求出 $N$ 的因数 $d$ ,再找到一对互质的 $(a,b)$ ,使得 $a+b-1=d$ ,就一定有一对 $(a\times k,b\times k)$ 满足条件。

接着就可以进行求解了!!!

我们只需要枚举所有的 $d$ ,并对于每一个 $d$ ,在满足 $a+b-1=d$ 的情况下枚举 $a,b$ ,只要 $a,b$ 互质,就产生了一组可行解。而由于 $a+b=d+1$ ,我们也可以枚举 $i$ ——$a,b$ 就为 $i,d+1-i$。

即求:
$$\sum_{d|n}\sum_{i=1}^d[\gcd(i,d+1-i)=1]$$
注意,此时我们会重复枚举 $(a,b)$ 和 $(b,a)$ ,因此我们需要将答案除以 $2$。

显然,由于 $\gcd$ 的性质,我们可以将 $d+1-i$ 加上 $i$,这样右边的 $\sum$ 就转化为了:
$$\sum_{i=1}^d[\gcd(i,d+1)=1]$$
然后我们惊奇的发现,这不就是 $\varphi(d+1)$ 吗!

于是原题即求:
$$\sum_{d|n}\varphi(d+1)$$
最后我们注意,在枚举 $d$ 时,若 $d$ 不为 $1$ ,我们只需要将其除以 $2$ 去重即可,但当 $d=1$ 时,有且仅有一种情况 $(1,1)$ ,因此我们统计时可以先忽略掉 $d=1$ 的情况,输出结果时 $+1$ 即可。

时间复杂度

枚举因数实际上可以优化为 $O(\sqrt n)$ ,但受线性筛的时间复杂度影响,最终时间复杂度为 $O(n)$。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5;
int phi[N],pri[N],cnt;
bool vis[N];
ll ans;
inline void prepare(int n){//线性筛求phi
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i]){phi[i]=i-1;pri[++cnt]=i;}
        for(int j=1;j<=cnt&&pri[j]*i<=n;j++){
            vis[pri[j]*i]=1;
            if(!(i%pri[j])){phi[i*pri[j]]=pri[j]*phi[i];break;}
            else phi[i*pri[j]]=(pri[j]-1)*phi[i];
        }
    }
}
int main(){
    int n;
    scanf("%d",&n);
    prepare(n+1);
    for(int i=2;i<=n;i++)//枚举n的因数
        if(!(n%i)) ans+=(phi[i+1]>>1);
    printf("%lld",ans+1);//答案加上d=1的情况
    return 0^0;
}

备注

线性筛求 $\varphi$ 可以参考 $Rogn$ 大佬的文章


月流华 岁遗沙 万古吴钩出玉匣