A simple Blog for wyx I've been down the bottle hoping.
1041: [HAOI2008]圆上的整点 数论
发表于: | 分类: Oi | 评论:0 | 阅读:48

神思路……根本想不到去取gcd啊……被解析几何害的太惨

下面是推导过程

$x^2+y^2=r^2$

$x^2=r^2-y^2 = (r+y)(r-y)$

令$d=\gcd(x+y,x-y)$,那么就有$(\frac{x}{d})^2 = \frac{r+y}{d}\times\frac{r-y}{d}$

我们知道$\gcd(\frac{r+y}{d},\frac{r-y}{d})$ 必然为1,也就是他们两个互质,然而又会发现他们的乘积是一个完全平方数,显然他俩都是完全平方数

然后……然后就好办了,令$r+y=a^2,r-y=b^2$,则有$r=\frac{d(a^2+b^2)}{2},y=\frac{d(a^2-b^2)}{2},x=dab$

然后先枚举一下$2*r$的一个约数作为$d$,再枚举$a^2$,最后判断就行了

注意下$a,b$不能同时为1,需要特判

#include <cmath>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const double eps = 1e-6;
const int N = 1e5+5;
LL r, ans, fac[N];
int cnt;

void get(LL x) {
    int i;
    for(i=1;(LL)i*i<x;++i) if(x%i==0) fac[++cnt] = i, fac[++cnt] = x/i;
    if((LL)i*i==x)  fac[++cnt] = i;
}

bool check(LL x) {
    double tmp = sqrt((double)x);
    if(fabs(floor(tmp+eps)-tmp)<eps) return true;
    return false;
}

int main() {
    cin >> r ;
    get(r<<1);
    for(int i=1;i<=cnt;++i) {
        LL left = (r+1)/fac[i];
        for(int j=1;(LL)j*j<left;++j){
            LL tmp1 = r*2/fac[i]-(LL)j*j;
            if(check(tmp1) && __gcd(tmp1,(LL)j*j)==1 && (LL)j*j != tmp1) ans ++;
        }
    }
    printf("%lld\n",(ans+1)*4);
}  
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP