【数论】等边三角形 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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注