c++ - NxM 网格上的平行四边形数

Question

我必须解决一个问题，当给定一个网格大小 N x M 时，我必须找到“可以放入其中”的平行四边形的数量，这样它们的每个坐标都是一个整数。

这是我的代码:

/*
      ~Keep It Simple!~
*/

#include<fstream>

#define MaxN 2005

int N,M;
long long Paras[MaxN][MaxN]; // Number of parallelograms of Height i and Width j
long long Rects; // Final Number of Parallelograms

int cmmdc(int a,int b)
{
while(b)
{
    int aux = b;
    b = a -(( a/b ) * b);
    a = aux;
}

return a;
}

int main()
{
freopen("paralelograme.in","r",stdin);
freopen("paralelograme.out","w",stdout);

scanf("%d%d",&N,&M);

for(int i=2; i<=N+1; i++)
    for(int j=2; j<=M+1; j++)
    {
        if(!Paras[i][j])
          Paras[i][j] = Paras[j][i] = 1LL*(i-2)*(j-2) + i*j - cmmdc(i-1,j-1) -2; // number of parallelograms with all edges on the grid + number of parallelograms with only 2 edges on the grid.
        Rects += 1LL*(M-j+2)*(N-i+2) * Paras[j][i]; // each parallelogram can be moved in (M-j+2)(N-i+2) places.
    }

printf("%lld", Rects);
}

示例:对于 2x2 网格，我们有 22 个可能的平行四边形。

我的算法有效并且正确，但我需要让它更快一点。我想知道这怎么可能。

附言我听说我应该预处理最大公约数并将其保存在一个数组中，这会将运行时间减少到 O(n*m)，但我不确定如何在不使用 cmmdc 的情况下做到这一点(最大公约数 ) 函数。

Answer 1

确保N不小于M:

if( N < M ){ swap( N, M ); }

利用循环中的对称性，您只需将 j 从 2 运行到 i:

for(int j=2; j<=min( i, M+1); j++)

你不需要额外的数组Paras，放弃它。而是使用临时变量。

long long temparas = 1LL*(i-2)*(j-2) + i*j - cmmdc(i-1,j-1) -2;
long long t1 = temparas * (M-j+2)*(N-i+2);
Rects += t1;
// check if the inverse case i <-> j must be considered
if( i != j && i <= M+1 ) // j <= N+1 is always true because of j <= i <= N+1
    Rects += t1;

替换此行:b = a -(( a/b ) * b); 使用余数运算符:

b = a % b;

缓存 cmmdc 结果可能是可能的，您可以使用某种筛选算法初始化数组:创建一个由 a 和 b 索引的二维数组，在每个位置放置“2”，其中 a 和 b 是 2 的倍数，然后在每个a和b是3的倍数的位置放一个“3”，以此类推，大致如下:

int gcd_cache[N][N];

void init_cache(){
    for (int u = 1; u < N; ++u){
        for (int i = u; i < N; i+=u ) for (int k = u; k < N ; k+=u ){
            gcd_cache[i][k] = u;
        }
    }
}

虽然不确定它是否有很大帮助。