题意
题目中给出了一个 $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$ 大佬的文章