Gym - 101845E (图形转换思维)

题意:给你个边长为n(1 <= n <= 50)的下图这种三角形,图形所有点构成集合。找多少对a,b满足条件,条件为:ab两点之间还有其他点。

Gym - 101845E (图形转换思维)

 

 题解:刚开始以为直接找规律就行,wa了两次发现可能会有斜着的。后来又想暴力跑一下就行了,但是坐标是double的怎么跑?然后发现转化成直的就行了。至于为什么想成这种,也说不清,这样画出来发现他们的性质确实一样,以后看见这图形记住好点,这种性质一个样。

然后枚举每两个点,求坐标差的gcd,如果大于1,则满足。这个为什么呢?在纸上画一下就知道,gcd表示的是以ab为顶点的线段可以被整分为gcd份。因为我们所有书都是整数。

Gym - 101845E (图形转换思维)

 

 

#include <bits/stdc++.h>
#define FOR(a, b, c) for(int a = b; a <= c; a++)
#define met(a, b) memset(a, b, sizeof(a))
#define mp make_pair
using namespace std;
typedef long long ll;
vector<pair<int, int> >q;
int main(){
    int n; cin >> n;
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= i; j++){
            q.push_back(mp(i, j));
        }
    }
    int tot = 0;
    for(int i = 0; i < q.size(); i++){
        for(int j = i+1; j < q.size(); j++){
            int x = abs(q[i].first - q[j].first);
            int y = abs(q[i].second - q[j].second);
            if(__gcd(x, y) > 1) tot++;
        }
    }
    cout << tot << endl;
    return 0;
}

 

上一篇:2019-9-10:渗透测试,基础学习,nmap扫描命令,php基本语法学习,笔记


下一篇:codeforces gym #101161F-Dictionary Game(字典树+树上删边游戏)