问题描述
给定平面上的两个格点p1=(x1,y1), p2=(x2,y2),线段p1p2上，除了p1和p2意外一共有几个格点？
问题分析
此题考查gcd的应用 res=gcd(abs(y2-y1),abs(x2-x1))-1 使用快速幂可以将两点之间的横坐标纵坐标进行均匀掐分，从而得到格点的个数
代码
#include <bits/stdc++.h>
using namespace std
;
typedef long long ll
;
ll
gcd(ll a
, ll b
);
int main()
{
ll x1
, y1
, x2
, y2
;
cin
>> x1
>> y1
>> x2
>> y2
;
ll res
= gcd(abs(x1
- x2
), abs(y1
- y2
)) - 1;
return 0;
}
ll
gcd(ll a
, ll b
)
{
return b
? gcd(b
, a
% b
) : a
;
}
