BZOJ 1041: [HAOI2008]圆上的整点

傷城~ 2022-07-29 08:41 138阅读 0赞

## 1041: \[HAOI2008\]圆上的整点 ##

Time Limit: 10 Sec Memory Limit: 162 MB  
Submit: 2951 Solved: 1296  
\[[Submit][]\]\[[Status][]\]\[[Discuss][]\]

## Description ##

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

## Input ##

r

## Output ##

整点个数

## Sample Input ##

4

## Sample Output ##

4

## HINT ##

n<=2000 000 000

#include<stdio.h>
    #include<cmath>
    #include<string.h>
    #define LL long long
    LL r;
    LL ans;
    LL gcd(LL x,LL y)
    {
    	return x%y==0?y:gcd(y,x%y);
    }
    bool check(LL y,double x)
    {
    	if(x==floor(x))
    	{
    		LL x1=(LL)floor(x);
    		if(gcd(x1*x1,y*y)==1&&x1*x1!=y*y)
    		{
    			return true;
    		}
    	}
    	return false;
    }
    int main()
    {
    	scanf("%lld",&r);
    	for(LL d=1;d<=sqrt(2*r);d++)
    	{
    		if((2*r)%d==0)
    		{
    			for(LL a=1;a<=(LL)sqrt(2*r/(2*d));a++)
    			{
    				double b=sqrt(((2*r)/d)-a*a);
    				if(check(a,b))ans++;
    			}
    			if(d!=(2*r)/d)
    			{
    				for(LL a=1;a<=(LL)sqrt(d/2);a++)
    				{
    					double b=sqrt(d-a*a);
    					if(check(a,b))
    					ans++;
    				}
    			}
    		}
    	}
    	printf("%lld\n",ans*4+4);
    	return 0;
    }

[Submit]: http://www.lydsy.com/JudgeOnline/submitpage.php?id=1041
[Status]: http://www.lydsy.com/JudgeOnline/problemstatus.php?id=1041
[Discuss]: http://www.lydsy.com/JudgeOnline/bbs.php?id=1041

发表评论取消回复

表情：

评论列表（有 0 条评论，138人围观）

还没有评论，来说两句吧...

相关阅读

相关【bzoj】1042: [HAOI2008]硬币购物

1042: \[HAOI2008\]硬币购物 Time Limit: 10 Sec Memory Limit: 162 MB Submit: 2371 Solved: 1

比眉伴天荒/ 2022年09月30日 15:59/ 0 赞/ 121 阅读

相关已知圆心，半径，角度，求圆上的点坐标

圆点坐标：(x0,y0) 半径：r 角度：a0 则圆上任一点为：（x1,y1） x1 = x0 + r \ cos(ao \ 3.14 /180

偏执的太偏执、/ 2022年08月21日 10:51/ 0 赞/ 373 阅读

相关 BZOJ 1041: [HAOI2008]圆上的整点

1041: \[HAOI2008\]圆上的整点 Time Limit: 10 Sec Memory Limit: 162 MB Submit: 2951 Solved

傷城~/ 2022年07月29日 08:41/ 0 赞/ 139 阅读

相关 bzoj4035【HAOI2015】数组游戏

题目描述有一个长度为N的数组，甲乙两人在上面进行这样一个游戏：首先，数组上有一些格子是白的，有一些是黑的。然后两人轮流进行操作。每次操作选择一个白色的格子，假设它的

淡淡的烟草味﹌/ 2021年12月23日 01:45/ 0 赞/ 179 阅读

相关【洛谷 P2512】 [HAOI2008]糖果传递（贪心）

[题目链接][Link 1] 环形均分纸牌。设平均数为\\(ave\\),\\(g\[i\]=a\[i\]-ave\\),\\(s\[i\]=\\sum\_\{j=1

深藏阁楼爱情的钟/ 2021年12月21日 06:37/ 0 赞/ 235 阅读

相关 BZOJ 2427: [HAOI2010]软件安装 tarjan + 树形背包

Code: include<bits/stdc++.h> using namespace std; define setIO(s) freope

迈不过友情╰/ 2021年11月17日 16:18/ 0 赞/ 239 阅读

相关 P2512 [HAOI2008]糖果传递

题目描述有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。输入输出格式输入格式：小朋友个数n

港控/mmm°/ 2021年09月30日 07:04/ 0 赞/ 323 阅读

相关题解 P2512 [HAOI2008]糖果传递

首先我们要用到一些[均分纸牌][Link 1]的思想(已经理解这种思想的大佬请跳过): 设\\(A\_i\\)表示第\\(i\\)个小朋友原有的糖果数量, 设\\(ave\

小鱼儿/ 2021年09月29日 11:56/ 0 赞/ 252 阅读

相关 [LUOGU] P4290 [BZOJ] 1055 [HAOI2008]玩具取名

题目描述某人有一套玩具，并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个字母用“WIN

小咪咪/ 2021年09月29日 02:50/ 0 赞/ 225 阅读

相关 Bzoj1042: [HAOI2008]硬币购物

Sol 容斥原理+背包处理出所有金币无限制条件凑成\(j\)元的方案数考虑计算 \(c\)只有\(4\)种，可以容斥一波就是无限制的总方案-\(1\)个硬币超出限制...

朱雀/ 2021年03月28日 15:40/ 0 赞/ 429 阅读