【数论】等边三角形 gym-101845E
传送门
题意是说个一个边长为n的等边三角形,由若干个边长为1的等边三角形拼起来。问有多少个点对,相连的直线经过交点。
把等边三角形看成一个等腰直角三角形,相当于变型一下。可以发现,当横纵坐标差值的gcd > 1的时候,点对是符合条件的。
数据只有50。直接暴力塞点然后判断就好。
不过队友在比赛的时候写的搜索,不知为何炸了。
#include<bits/stdc++.h>
using namespace std;
vector<int> a;
int main()
{
int n; cin >> n;
for(int i = 1; i <= n + 1; i++)
for(int j = 1; j <= i; j++) a.push_back(i << 16 | j);
long long ans = 0;
for(int i = 0; i < a.size(); i++)
{
int x = a[i] >> 16, y = a[i] & ((1 << 16) - 1);
for(int j = i; j < a.size(); j++)
{
int u = a[j] >> 16, v = a[j] & ((1 << 16) - 1);
if(abs(__gcd(x - u, y - v)) > 1) ans++;
}
}
cout << ans;
}
发表评论