迷失方阵
给你一个N*M的方阵,你能告诉它这个方阵有多少个正方形吗?
eg:1x1矩阵 1个正方形
2x3矩阵 8个正方形
代码很简洁,但是数学规律需要多拿笔画一下,才能发现。
#include<stdio.h>
#include<math.h>
long long square(long long,long long);
int main(){long long count;long long M,N;while(scanf("%d %d",&M,&N)!=EOF){count=M*N+(fabs(M-N)+1)*square(M,N);//见图一printf("%d\n",count%1000000007);//count不大于1000000007时,都不影响其值}
}
//eg:5x7的矩阵,计算5x5的矩阵可以组成多少个正方形(但是不计算每一个小格子)
//eg:5x2的矩阵,计算2x2的矩阵可以组成多少个正方形(但是不计算每一个小格子)
long long square(long long m,long long n){long long sum=0,min;if(m>=n){min=n;}else{min=m;}for(int i=1;i<min;i++){sum+=(min-i)*(min-i);//见图二}return sum;
}
本题:主要是个数学问题:找规律规律,自己多拿笔数一下正方形个数,就能发现规律了,光看解释可能会被绕晕过去。
m*n方阵的正方形个数等于下列式子:
而式子中的规律的值,请看下图解释:
注意:在某些Online Judge系统上面跑本代码,会出现Time Limit Exceeded错误,指出:运行超时。
在Clion编译器中,运行时间几乎并不会受到影响。瞬间就能计算出结果。