很有意思的一个组合数学题。
整个题的最核心的思想就是，两个线段共线的判断！只要有两个点就可以确定一条线段（直线），那么只要再多一个点就可以确定这个点是否在和当前的这条线段共线了！所以两种算法的思想都在于一个2
第一种方法：最纠结的问题还是在于，怎么去重。想到了枚举角度的方法却没有想到怎么去重，还是思维不行。第一种方法是每次枚举所有可能的矩形，然后计算对角线的数量，这个很好算也就是有多少个矩形，直接(n-i+1)*(m-j+1)就行了。但是我们考虑的时候首先只考虑gcd(i,j)==1的情况，这种情况一定说明这种对角线的角度第一次出现（因为我们从小到大枚举i和j），所以对答案贡献为正，还有一种情况是gcd(i,j)==2，这说明之前已经出现过了这种对角线，所以这里要减去对应的数量，注意这里是最重要的：减去的是对应的数量，然后其他的gcd值不用+也不用-。原因就在于，如果你有一个4*4的或者3*3的矩形对角线重算了，那么在清除gcd为2的那一步当中其实就已经清除了所有的重复对角线！因为这个2会按照不同的起始点一直推下去。
第一种方法代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int g[305][305];
void pre()
{
for(int i=1;i<=300;i++)
for(int j=1;j<=300;j++)
g[i][j]=gcd(i,j);
}
int main()
{
int n,m;
LL tmp;
pre();
while(~scanf("%d%d",&n,&m)&&n)
{
LL ans=0;
n--,m--;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
int a=i,b=j;
tmp=1LL*(n-i+1)*(m-j+1);
if(g[i][j]==1)
ans+=tmp;
else if(g[i][j]==2)
ans-=tmp;
}
}
printf("%lld\n",2*ans);
}
return 0;
}
第二种方法：递推刷表。这种递推中很重要的是定义状态，类似于dp吧，每次要递推的话一定得是有大问题包含小问题的关系在里面。假如我们定义这种cnt[i][j]就是长宽为ij的点阵对应的答案的话，那么可以得到一个递推式cnt[i][j]=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1]+贡献(i,j)，最后一项表示仅仅点ij对答案的贡献，这里的二维前缀和计算也很常用。所以现在的问题就转化成了如何计算单独考虑ij点的时候对于整个答案的贡献。这个贡献一定跟经过ij点的斜线数量有关系，可以设g[i][j]为长宽为ij的矩形点阵里，只经过左上角到其他点的只经过两个端点的线段数量，那么这个也可以二维递推g[i][j]=g[i-1][j]+g[i][j-1]-g[i-1][j-1]+(gcd(i,j)==1);最后一项利用的是斜率不能重复计算。有了这个之后可以先把这个贡献加上cnt，但是这时候会有一个问题，计入的新的线段有可能会和之前的已经有的线段“接上”，导致重复计算，如何去重？这里就是整个算法最精彩的部分，不要从已经计算的线段上考虑，从新加入的线段上考虑：如果新加入的一条线段和之前的重在一条直线上了，那么这条新加入的线段一定在[i/2][j/2]这个矩形内部，如果他超过了这个大小，那么除了这个小矩形之外ij矩形剩下的部分不足以再划分出来一个这样的矩形，所以不可能存在那些重复计算的线段（我们保证对于g[i][j]他的意义是矩形内没有重点，所以要重只可能是之外），反过来，只要一条线段在这个小矩形内部，他一定会被重复计算，因为一定可以从剩下的区域中划分出来一个同样的句型里面拥有这条对角线。
第二种方法代码：
#include<bits/stdc++.h>
int N,M;
long long cnt[MAXN][MAXN],sum[MAXN][MAXN];
int gcd(int a,int b)
{
return a%b?gcd(b,a%b):b;
}
void init()
{
for(int i=1; i<MAXN; i++)
for(int j=1; j<MAXN; j++) cnt[i][j]=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1]+(gcd(i,j)==1?1:0);
for(int i=1; i<MAXN; i++)
for(int j=1; j<MAXN; j++)
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+cnt[i][j]-cnt[i/2][j/2];
}
int main()
{
init();
while(scanf("%d%d",&N,&M),N||M)
{
printf("%lld\n",2*sum[N-1][M-1]);
}
return 0;
}