Peekaboo(2019年上海网络赛K题+圆上整点)

目录
  • 题目链接
  • 题意
  • 思路
  • 代码

题目链接

传送门

题意

你的位置在\(O(0,0)\)，\(A\)的位置为\((x_1,y_1)\)，\(B\)的位置为\((x_2,y_2)\)，现在已知\(a=OA,b=OB,c=AB\)，问你有多少对满足题意的\(A,B\)。

思路

由于\(a,b,c\)都是整数，\(O,A,B\)的坐标为整数，所以如果存在满足题意的点对，那么\(a,b\)一定是勾股数，且\(a^2=x_1^2+y_1^2,b=x_2^2+y_2^2\)，所以我们可以通过求出所有的\((x_1,y_1),(x_2,y_2)\)然后看\(c\)是否等于\(AB\)。

对于\(a^2=x^2+y^2\)，此时要推荐一个优秀的视频，根据这个视频里面说的即可解决这题。

如果没有时间看那么长的视频的可以看洛谷圆上整点的板题的题解里面的解释。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
typedef pair pLL;
typedef pair pLi;
typedef pair pil;;
typedef pair pii;
typedef unsigned long long uLL;

#define fi first
#define se second
#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["< vec[maxn];
vector A, B;

bool check(LL x1, LL y1, LL x2, LL y2) {
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) == c * c;
}

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

void solve(LL x, LL d, vector &vec) {
    if(x == 1 || x % 4 != 1) return;
    for(int s = 1; 2LL * s * s <= x; ++s) {
        LL tmp = x - 1LL * s * s;
        int t = (int)sqrt(tmp);
        if(1LL * t * t != tmp) ++t;
        if(1LL * s * s + 1LL * t * t != x) continue;
        if(gcd(s, t) != 1) continue;
        if(s >= t) continue;
        vec.emplace_back((1LL * t * t - 1LL * s * s) * d, 2 * d * s * t);
    }
}

void GaussInteger(LL x, vector &vec) {
    for(int i = 1; 1LL * i * i <= x; ++i) {
        if(x % i) continue;
        solve(x / i, i, vec);
        if(1LL * i * i != x) solve(i, x / i, vec);
    }
}

void fillpoint(LL x, vector &vec) {
    int num = vec.size();
    for(int i = 0; i < num; ++i) {
        vec.emplace_back(vec[i].se, vec[i].fi);
    }
    for(int i = 0; i < 2 * num; ++i) {
        vec.emplace_back(vec[i].fi, -vec[i].se);
        vec.emplace_back(-vec[i].fi, vec[i].se);
        vec.emplace_back(-vec[i].fi, -vec[i].se);
    }
    vec.emplace_back(x, 0);
    vec.emplace_back(-x, 0);
    vec.emplace_back(0, x);
    vec.emplace_back(0, -x);
}

int main() {
#ifndef ONLINE_JUDGE
    FIN;
    time_t startclock = clock();
#endif // ONLINE_JUDGE
    scanf("%d", &t);
    while(t--) {
        scanf("%lld%lld%lld", &a, &b, &c);
        cnt = 0;
        A.clear(), B.clear();
        GaussInteger(a, A), GaussInteger(b, B);
        fillpoint(a, A), fillpoint(b, B);
        for(auto num1:A) {
            for(auto num2:B) {
                if(check(num1.fi, num1.se, num2.fi, num2.se)) {
                    vec[++cnt] = make_pair(num1, num2);
                }
            }
        }
        sort(vec + 1, vec + cnt + 1);
        printf("%d\n", cnt);
        for(int i = 1; i <= cnt; ++i) {
            printf("%d %d %d %d\n", vec[i].fi.fi, vec[i].fi.se, vec[i].se.fi, vec[i].se.se);
        }
    }
#ifndef ONLINE_JUDGE
    time_t endclock = clock();
    printf("It costs %.3fs\n", 1.0 * (endclock - startclock) / CLOCKS_PER_SEC);
#endif // ONLINE_JUDGE
    return 0;
}
迷之数论比赛题解感想

相关

标签