注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1041][HAOI2008]圆上的整点  

2014-10-10 19:11:29|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1041: [HAOI2008]圆上的整点

脑洞数学题
真不知道怎么能想出来
感觉老是看题解没什么资格发题解啊……

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;

typedef long long LL;
int n,m,ans;
LL scan(){LL i = 0;scanf("%I64d",&i);return i;}
LL gcd(LL a,LL b){return a?gcd(b%a,a):b;}
void check(LL x){
LL sqx = sqrt(x/2),a2,b,b2;
for(LL a = 1;a<=sqx;a++){
a2 = a*a;
b2 = x - a2;
b = sqrt(b2);
if(b*b == b2 && gcd(a2,b2)==1 && a2!=b2)ans++;
}
}
int main(){
//int i,j;
LL r = scan(),sqn;
sqn = sqrt(r*2);
for(LL i = 1;i <= sqn;i++)
if(2*r % i ==0){
check(i);
check(2*r / i);
}
printf("%d\n",(ans+1)*4);
return 0;
}

GTY的题解:
[Analysis]
题目倒是很简洁明了……但是有点让人无从下手
我们一步一步来分析:
首先写出式子 X ^ 2 + Y ^ 2 = R ^ 2
移项 Y ^ 2 = R ^ 2 - X ^ 2
          = (R + X)(R - X)
设 d = GCD(R + X, R - X)
则 Y ^ 2 = d ^ 2 * (R + X) / d * (R - X) / d
设 A = (R + X) / d, B = (R - X) / d
则 A != B 且 GCD(A, B) = 1
且 Y ^ 2 = d ^ 2 * A * B
由于Y ^ 2 是完全平方数, d ^ 2也是完全平方数, 而A, B互质,所以A, B都是完全平方数
设 A = a ^ 2, B = b ^ 2
则 a ^ 2 + b ^ 2 = 2 * R / d
说明 d 是 2 * R 的因数,以此可以在[1, sqrt(2 * R)]的范围内枚举i,当2 * R % i == 0时,i 和 2 * R / i都是2 * R 的因数。确定 2 * R / d 的值,假设a < b,我们再在[1, sqrt((2 * R / d) / 2)]的范围内枚举a, 算出对应的 A, b, B, 如果A, B都是完全平方数而且 A != B, GCD(A, B) == 1则方案数加1。这是一个象限的方案数,最后再* 4 再加上坐标轴上的4个即可
[Pay Attention]
用long long啊用long long!
注意以后求勾股数相关的都可以利用这里推出的结论…… 
完全Ctrl + C Ctrl + V

  评论这张
 
阅读(747)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017