题目

题目描述

求一个给定的圆($x^2+y^2=r^2$)，在圆周上有多少个点的坐标是整数。

输入格式

输出格式

整点个数

样例输入

4

样例输出

4

说明

$n\le2000000000$

题解

转自这篇文章
这里先只考虑x，y都大于0的情况

如果$x^2+y^2=r^2$，则$(r-x)(r+x)=y^2$

令$d=gcd(r-x,r+x)$

则$(r-x)/d$与$(r+x)/d$一定互质，二者相乘为完全平方数，则二者一定都为完全平方数

令$r-x=d\times a^2$,$r+x=d\times b^2$

则显然有a,b互质，a<b

其中 $x=\frac{d(b^2-a^2)}{2}$
$y=d\times a\times b$
$r=\frac{d\times (a^2+b^2)}{2}$

枚举$2r$的因数$d$，对于每个d我们用$O(\sqrt{\frac{r}{d}})$的时间枚举$a$ 代入$r$的计算式得出$b^2$ 计算$b^2$是否为完全平方数及$a^2$与$b^2$是否互质

这样可以枚举出一个象限内的整点个数然后输出$(ans+1)\times 4$即可

代码

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
ll r,ans;

ll gcd(ll a,ll b){
    return b? gcd(b,a%b):a;
}

void solve(ll x){
    ll top=(ll)sqrt(x/2);
    for(int a=1;a<=top;a++){
        ll A=a*a;
        ll B=x-A;
        ll b=(ll)sqrt(B);
        if(gcd(A,B)==1&&B==b*b&&A!=B){
            ans++;
        }
    }
}

int main(){
    cin>>r;
    ll top=(ll)sqrt(2*r);
    for(int i=1;i<=top;i++){
        if(2*r%i==0){
            solve(i);
            solve(2*r/i);
        }
    }
    cout<<ans*4+4;//+4个坐标轴上的点
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

typedef long long ll;

ll r,ans;

ll gcd(ll a,ll b){

return b? gcd(b,a%b):a;

}

void solve(ll x){

ll top=(ll)sqrt(x/2);

for(int a=1;a<=top;a++){

ll A=a*a;

ll B=x-A;

ll b=(ll)sqrt(B);

if(gcd(A,B)==1&&B==b*b&&A!=B){

ans++;

}

int main(){

cin>>r;

ll top=(ll)sqrt(2*r);

for(int i=1;i<=top;i++){

if(2*r%i==0){

solve(i);

solve(2*r/i);

}

cout<<ans*4+4;//+4个坐标轴上的点

return 0;

}

附

这题还有一个更美妙的解法，0msAC，具体就是下面这个视频
如果你不想花时间看的话也可以看这篇文章，基本上就是整个视频对我们有用的知识的提炼

代码如下:

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long r;
    int ans=1;
    cin>>r;
    for(int i=2;i<=sqrt(r);i++){
        int p=0;
        while(r%i==0){
            if(i%4!=3){
                p+=2;
            }
            r/=i;
        }
        if(i!=2)
            ans*=(p+1);
    }
    if(r!=1){
        if(r%4!=3){
            ans*=3;
        }
    }
    cout<<ans*4<<endl;
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int main(){

long long r;

int ans=1;

cin>>r;

for(int i=2;i<=sqrt(r);i++){

int p=0;

while(r%i==0){

if(i%4!=3){

p+=2;

}

r/=i;

}

if(i!=2)

ans*=(p+1);

}

if(r!=1){

if(r%4!=3){

ans*=3;

}

cout<<ans*4<<endl;