北京建设银行网站田村,广州室内设计公司排行榜,网站开发模式名词,安徽工程信息造价网正题
题目链接:https://www.luogu.com.cn/problem/P2508 题目大意
一个在(0,0)(0,0)(0,0)的圆心#xff0c;半径为rrr#xff0c;求圆有多少个整点。 1≤r≤21091\leq r\leq 2\times 10^91≤r≤2109 解题思路
设这个点为(x,y)(x,y)(x,y)#xff0c;那么有x2y2r2x^2y^2r^2…正题
题目链接:https://www.luogu.com.cn/problem/P2508 题目大意
一个在(0,0)(0,0)(0,0)的圆心半径为rrr求圆有多少个整点。
1≤r≤2×1091\leq r\leq 2\times 10^91≤r≤2×109 解题思路
设这个点为(x,y)(x,y)(x,y)那么有x2y2r2x^2y^2r^2x2y2r2 x2r2−y2(ry)(r−y)x^2r^2-y^2(ry)(r-y)x2r2−y2(ry)(r−y) 设rya×d,r−yb×d,gcd(a,b)1rya\times d,r-yb\times d,\gcd(a,b)1rya×d,r−yb×d,gcd(a,b)1因为x2x^2x2为完全平方数所以au2,bv2au^2,bv^2au2,bv2 x2u2v2d2⇒xu×v×dx^2u^2v^2d^2\Rightarrow xu\times v\times dx2u2v2d2⇒xu×v×d 2r(v2u2)×d2r(v^2u^2)\times d2r(v2u2)×d 所以我们枚举2r2r2r的因数ddd然后再枚举一个v2v^2v2就行了。 code
#includecstdio
#includecstring
#includealgorithm
#includecmath
#define ll long long
using namespace std;
ll n,m,r,ans;
void solve(ll d){for(ll s1;s*sr/d;s){ll tsqrt(r/d-s*s);if(s*st*t!r/d)continue;if(__gcd(s,t)1)continue;ll x(s*s-t*t)/2ll*d;ll yt*s*d;if(x0y0x*xy*yr/2ll*r/2ll)ans2;}return;
}
signed main()
{scanf(%lld,r);rr*2ll;for(ll i1;i*ir;i)if(r%i0){solve(i);if(i*i!r)solve(r/i);}printf(%lld\n,(ans1)*4ll);return 0;
}
