基础算法题—— honoka和格点三角形

分手后的思念是犯贱 2023-07-04 11:12 8阅读 0赞

# 基础算法题—— honoka和格点三角形 #

## 前言 ##

本人为一名普通二本学校自动化专业的大二学生，对编程有着少许兴趣。  
第一次写博客，希望能与老铁们交流自己不成熟的见解。

## 做题心得 ##

这道算法题并没有运用到多么高深的算法，仅考查了对计数算法的掌握。  
很可惜的是，尽管在做题时我将所有情况都考虑到了，但是却因为不会将计算步骤分步求余而错失了AC的机会。好了，废话不多说了，让我们进入正题。

## honoka和格点三角形题目 ##

honoka最近在研究三角形计数问题。  
她认为，满足以下三个条件的三角形是“好三角形”。  
1.三角形的三个顶点均为格点，即横坐标和纵坐标均为整数。  
2.三角形的面积为1。  
3.三角形至少有一条边和x轴或y轴平行。  
honoka想知道，在平面中选取一个大小为n\*m的矩形格点阵，可以找到多少个不同的“好三角形”？由于答案可能过大，请对1000000007取模。  
输入描述:  
两个正整数n和m（ 2 ≤n,m≤10^9）  
输出描述:  
面积为1的格点三角形的数量，对 10^9+7取模的结果。  
\#示例1  
输入：  
2 3  
输出：  
6  
说明：  
格点如下：  
| \* | \* | \* |  
| \* | \* | \* |  
不妨设左下角坐标为(1,1)，右上角坐标为到(3,2)。  
那么三点坐标可选：  
（1，1）（1，2）（3，1）  
（1，1）（1，2）（3，2）  
（1，1）（2，2）（3，1）  
（1，1）（3，1）（3，2）  
（1，2）（2，1）（3，2）  
（1，2）（3，1）（3，2）  
所以共有6个。

\#示例2  
输入：  
100 100  
输出：  
7683984  
[牛客网题目链接][Link 1]

## 题目分析 ##

通过对该题中对三角形三条件的分析，以及三角形的面积公式：S=（L\*H）/2。我们可以了解到要满足“好三角形”，要符合L=2，H=1或者L=1，H=2。（在这里的L，我们可以理解为始终平行于x轴或y轴，防止底和高混淆）另外只有当n>=3和m>=2或者n>=2和m>=3成立时才可能出现“好三角形”。例如在n=2,m=2下，没有“好三角形”。

### 第一种情况——①n为底，非直角三角形而且L=2、②m为底，L=1 ###

我们可以将第一种情况中的“好三角形”再细分为：非直角三角形而且L=2的“好三角形”、L=1的“好三角形”。  
为了使公式更容易理解，我将会把公式的来源采用分骤的方式，逐步讲解。（以n=4, m=3为例）

#### ①n为底，非直角三角形而且L=2 ####

DYS=((n-2) * (m-1) * (n-2)) * 2

步骤1：(n-2)乘以(m-1)为选择L=2、而且平行与Y轴的情况：  
（没有将（3.1）~（3.4）作为底，因为三角形可以反向，我们取其中一个方向，结果再乘以2即可）  
![选底][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]  
步骤2：(n-2) \* (m-1) 乘以(n-2)为当底所对应的非直角三角形的情况：  
注意：这个地方是不可取直角三角形，我们将它归为另外的情况。  
![底为2的“好三角形”][2]  
步骤3：(n-2) \* (m-1) \* (n-2)乘以2，因为三角形可以反向，我们将同一方向的三角形乘以2即可。  
![反向][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70 1]  
以上就是非直角三角形而且L=2的“好三角形”全部个数

#### ②m为底，L=1 ####

FS=(n-2) * (m-1) * m * 2

步骤1：(n-2)乘以(m-1)为选择L=1、而且平行与X轴的情况：  
（没有将（1.3）~（3.3 ）、（1 .4~1.4）作为底，因为三角形可以反向，我们取其中一个方向，结果再乘以2即可）  
![选底][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70 2]  
步骤2：(n-2) \* (m-1)乘以m,中的m为每个底对应符合点击的顶点。  
![底为1的“好三角形”][1]  
步骤3：(n-2) \* (m-1) \* m乘以2因为三角形可以反向，我们将同一方向的三角形乘以2即可。  
![反向][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70 3]

### 第二种情况——①m为底，非直角三角形而且L=2、②n为底，L=1 ###

与第一种情况相似，只是将m与n交换计算而已,这里就不再赘述。  
n=4，m=3算出的结果为70。

### 取模运算法则： ###

1.  ( a + b ) % c = ( ( a % c ) + ( b % c ) ) % c
2.  ( a \* b ) % c = ( ( a % c ) \* ( b % c ) ) % c
3.  ( a – b ) % c = ( ( a % c ) – ( b % c ) ) % c  
    （该取模对计算结果由为重要，会影响你输入较大数据求值过程进行是否顺利）

最后附上算法代码：

//在可以求余中，可以将计算过程分成多个阶段
    //每个阶段的计算值都可以先求余
    //因为最后的值关键看得是余数
    //所以只要保留余数,就不影响计算结果 
    #include<stdio.h>
    const int mod = 1e9+7;
    int main()
    { 
    	long int n, m;
    	scanf("%d%d", &n, &m);
    	long long ZJS, ZJH , FH, FS;
    	long long int sum;
    	FH=0;FS=0;
    	ZJH=0;ZJS=0;
    	if(n>=3)
    	{ 
    		FS=(n-2)*(m-1)%mod;
    		FS=(FS*(n-2)*2)%mod;	//n为底，非直角三角形而且L=2
    		ZJS=(n-2)*(m-1)%mod;
    		ZJS=(ZJS*m*2)%mod;		//m为底，L=1
    	}
    	if(m>=3)
    	{ 
    		FH=((m-2)*(n-1))%mod;
    		FH=(FH*(m-2)*2)%mod;	//m为底，非直角三角形而且L=2
    		ZJH=((m-2)*(n-1))%mod;
    		ZJH=(ZJH*n*2)%mod;		//n为底，L=1
    	}
    	sum=(FS+ZJS+FH+ZJH)%mod;
    	printf("%d", sum);
    	
    	return 0;
    }

## 总结 ##

题目一开始理解可能有点困难，但是只要坚持下去，到后面思路就会越来越清晰。这道算法题只是分了四部分求不同情况下的“好三角形”，最后将它们加起来就得到最终结果。  
第一次写博客，解题的图可能太过潦草，如果有更好的作图方式，还请大佬教下小郑。  
如果内容有错误的地方，希望各位老铁批评指正，大家一起进步、学习。

### 如果觉得该文章对你有用的话，可以给我一个大大的赞喔！！ ###

#### 老铁的关注是鼓励我写博客的最大动力~ ####

![被代码吃了][20200223145954681.png]

[Link 1]: https://ac.nowcoder.com/acm/contest/3002/A
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200210153558874.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70
[2]: https://img-blog.csdnimg.cn/20200210153751842.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200210154050799.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200210155111655.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70
[1]: https://img-blog.csdnimg.cn/2020021015570455.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200210155937665.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70
[20200223145954681.png]: https://img-blog.csdnimg.cn/20200223145954681.png