题目描述

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

输入

只有一个正整数n,n<=2000 000 000

输出

整点个数

样例输入

4

样例输出

4


题解

数论

#include <cmath>
#include <cstdio>
typedef long long ll;
ll judge(ll k)
{
ll t = (ll)sqrt(k);
return t * t == k ? t : 0;
}
ll gcd(ll a , ll b)
{
return b ? gcd(b , a % b) : a;
}
ll calc(ll k)
{
ll i , t , ans = 0;
for(i = 1 ; i * i <= k / 2 ; i ++ )
{
t = judge(k - i * i);
if(t && gcd(i , t) == 1) ans ++ ;
}
return ans;
}
int main()
{
ll n , i , ans = 0;
scanf("%lld" , &n);
for(i = 1 ; i * i <= 2 * n ; i ++ )
{
if(2 * n % i == 0)
{
ans += calc(i);
if(i * i != 2 * n) ans += calc(2 * n / i);
}
}
printf("%lld\n" , ans * 4);
return 0;
}

最新文章

  1. Nginx/Apache服务连接数梳理
  2. web前端本地测试方法
  3. 设计模式之Iterator模式(2)
  4. js一些稀奇古怪的写法-带你装逼带你飞
  5. Objective-C传递数据小技巧
  6. java基础-四种方法引用
  7. Fiddler中Response 的Raw乱码问题解决
  8. MyEclipse2015上传项目到GitHub(很详细)
  9. Kylin系列之二:原理介绍
  10. Ubuntu16.04安装NVIDA驱动和CUDA
  11. SpringBoot 配置静态资源映射
  12. Python全栈开发之路 【第十七篇】:jQuery的位置属性、事件及案例
  13. Xcode真机调试失败:The identity used to sign the executable is no longer valid
  14. numpy最大值和最大值索引
  15. PAT A1099 Build A Binary Search Tree (30 分)——二叉搜索树,中序遍历,层序遍历
  16. eclipse 安装报错
  17. 5个基于Web的建模工具
  18. kindEditor富文本编辑器
  19. Python-Cpython解释器支持的进程与线程
  20. BZOJ 1492 [NOI2007]货币兑换Cash:斜率优化dp + cdq分治

热门文章

  1. iptables 防火墙详解
  2. Object.prototype.toString的应用
  3. fread, fwrite - 二进制流的输入/输出
  4. 2018.5.17 oracle函数查询
  5. mac 扫描存活IP段
  6. python剑指offer系列二叉树中和为某一值的路径
  7. flock文件锁
  8. Linux磁盘与文件管理系统
  9. Java-读取txt生成excel
  10. 使用code::blocks编译windows的dll链接库