Codeforces Round #736 (Div. 2) F1. Gregor and the Odd Cows (Easy)（皮克定理）

定理）"/>

Codeforces Round #736 (Div. 2) F1. Gregor and the Odd Cows (Easy)（皮克定理）

链接 F1. Gregor and the Odd Cows (Easy)

题意

简单版本的题中的坐标都是偶数
给出 n n n 个坐标点，其他坐标点都是🐂，三个坐标点是肯定可以构成一个三角形的，问构成的三角形里有奇数个🐂；

思路

首先很容易想到皮克定理， 2 S = 2 a + b − 2 2S = 2a + b - 2 2S=2a+b−2，其中 S S S 是三角形坐标， a a a 是三角形内部的点， b b b 为三角形的边上的格点数；

把式子转化一下 2 S = b + 2 ( a − 1 ) 2S = b + 2(a - 1) 2S=b+2(a−1) ；

设 A = 2 S A = 2S A=2S， B = b B = b B=b ，式子两边对 4 4 4 取模，可以发现 A ≡ B m o d 4 A\equiv B mod 4 A≡Bmod4，可以发现 B B B 是 4 4 4 的倍数；

对于两个坐标点 ( x 1 , y 1 ) , ( x 2 , y 2 ) ( x_1 , y_1 ) , ( x_2 , y_2 ) (x1​,y1​),(x2​,y2​)，连线上坐标点为整数的个数为 gcd ⁡ ( ∣ x 2 − x 1 ∣ , ∣ y 2 − y 1 ∣ ) \gcd(|x_2-x_1|,|y_2-y_1|) gcd(∣x2​−x1​∣,∣y2​−y1​∣)；

因为坐标点都是偶数，所以求得的 gcd ⁡ ( ∣ x 2 − x 1 ∣ , ∣ y 2 − y 1 ∣ ) m o d 4 = 0 o r 2 \gcd(|x_2-x_1|,|y_2-y_1|)mod4=0 or 2 gcd(∣x2​−x1​∣,∣y2​−y1​∣)mod4=0or2

即 B m o d 4 = 0 o r 2 Bmod4 = 0or2 Bmod4=0or2，只要找到 B m o d 4 = 0 Bmod4=0 Bmod4=0的情况就好了；

AC代码

#include <bits/stdc++.h>
#define mes memset
#define mec memcpy
#define x first
#define y second
#define pb push_back
#define be(x) (x).begin(), (x).end()
#define cl(x) memset((x), 0, sizeof (x))
#define sz(x) (int)(x).size()using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll,ll> PLL;const double pi = acos(-1);
const double eps = 1e-8;
const int N = 200010;
const int null = 0x3f3f3f3f,INF = 1e9;
const ll mod = 998244353;int n;
ll cnt[5][5];
vector<PII> v = {{0, 0}, {0, 2}, {2, 0}, {2, 2}};//预处理出%4的结果int check(int x1, int y1, int x2, int y2){if (x1 == x2 && y1 == y2) return 0;return 2;
}int main(){cin >> n;for (int i = 1; i <= n; i ++){int x, y;cin >> x >> y;//模4方便处理cnt[x % 4][y % 4] ++;}ll ans = 0;for (auto i : v){for (auto j : v){for (auto k : v){if (i <= j && j <= k){int d1 = check(i.x, i.y, j.x, j.y);//i-j的边上的整点数int d2 = check(k.x, k.y, j.x, j.y);//k-j············int d3 = check(i.x, i.y, k.x, k.y);//i-k············if (!((d1 + d2 + d3) % 4)){//极其简单的组合数if (i == j && j == k) ans += cnt[i.x][i.y] * (cnt[i.x][i.y] - 1) * (cnt[i.x][i.y] - 2) / 6;else if (j == k) ans += cnt[j.x][j.y] * (cnt[j.x][j.y] - 1) / 2 * cnt[i.x][i.y];else if (i == k) ans += cnt[i.x][i.y] * (cnt[i.x][i.y] - 1) / 2 * cnt[j.x][j.y];else ans += cnt[i.x][i.y] * (cnt[i.x][i.y] - 1) / 2 * cnt[k.x][k.y];}}}}}cout << ans << endl;
}

其实还写了一种做法，就是不知道为什么会过掉；

#include <bits/stdc++.h>
#define mes memset
#define mec memcpy
#define x first
#define y second
#define pb push_back
#define be(x) (x).begin(), (x).end()
#define cl(x) memset((x), 0, sizeof (x))
#define sz(x) (int)(x).size()using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll,ll> PLL;const double pi = acos(-1);
const double eps = 1e-8;
const int N = 200010;
const int null = 0x3f3f3f3f,INF = 1e9;
const ll mod = 998244353;int n;
int cnt[5];int main(){cin >> n;for (int i = 1; i <= n; i ++){int x, y;cin >> x >> y;if (x % 4 == 0 && y % 4 == 0) cnt[0] ++;else if (x % 4 == 2 && y % 4 == 2) cnt[1] ++;else if (x % 4 == 2 && y % 4 == 0) cnt[2] ++;else cnt[3] ++;}ll ans = 0;for (int i = 0; i < 4; i ++) ans += (ll)cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) / 6;for (int i = 0; i < 4; i ++){for (int j = 0; j < 4; j ++){if (i == j) continue;ans += (ll)cnt[i] * (cnt[i] - 1) / 2 * cnt[j];}}cout << ans << endl;
}

END