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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1041】【HAOI2008】【圆上的整点】  

2014-03-02 19:07:54|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   这么短的题目一定很难...咱这种蒟蒻想半天没想出一个解法来(除了暴力以外...)
   首先可以肯定的是咱们只需要计算4分之1个圆即可,又由于对称性可以算8分之一个圆....
   然后就不会了...
   这一定是数学题!!@%#!
   实际上就是几个勾股数...(其实就是咱不会...)
  推导一下
   设 x^2+y^2=r^2
   我们有 x^2=(r+y)(r-y)
   设 gcd(r+y,r-y)=d
   并设 m*d=r+y, n*d=r-y
   我们有 m*n=(x/d)^2
   上面提到过 gcd(r+y,r-y)=d,所以 m,n互质。
   m,n互质,它们相乘得到完全平方数。
  则m,n都是完全平方数。
  不妨设 m=u^2 n=v^2
  代入 r+y=md 与 r-y=nd 有
  r+y=u^2*d 
 r-y=v^2*d
  两式相加得到
 2r=(u^2+v^2)*d
  u可以确定m,v可以确定n,然后 m,n,d可以确定 r+y 和 r-y 然后x,y就确定了。
 也就是说每一个 u,v,d对应一组解 x,y
 首先得枚举d。
 枚举d为1~sqrt(2r)就可以求出2r的所有因数。
 然后 对于每一个符合条件 的 有两种情况 d=d 或者 d=2R/d
 两种情况都可以求出 u^2+v^2 的数。
 设 u<v 我们有 2*u^2<2r/d 即 u<sqrt(2r/2d),我们枚举u即可算出一个v^2,判断即可。
 判断的条件:1)v>u 2)u,v互质。
 然后这一题RE了两次,原因是变量没开int64...果然又是沙茶。
==============================

program bzoj1041;
var r,ans:int64;

function gcd(a,b:longint):longint;
var t:longint;
begin
 while true do
 begin
  if b=0 then exit(a)
         else begin
              t:=a;
              a:=b;
              b:=t mod a;
              end;
 end;
end;

function gcd(a,b:int64):int64;
var t:int64;
begin
  while true do
  begin
   if b=0 then exit(a)
          else begin
               t:=a;
               a:=b;
               b:=t mod a;
               end;
  end;
end;

procedure init;
var i,u:longint;
    d,v:int64;
begin
  read(r);
  r:=r*2;
  ans:=0;
  for i:=1 to trunc(sqrt(r)) do
   if r mod i=0 then
    begin
      d:=i;
      for u:=1 to trunc(sqrt(d/2)) do
       begin
         v:=trunc(sqrt(d-u*u));
         if (u*u+v*v=d)and(gcd(u,v)=1)and(u<v)then inc(ans);
       end;
      if r div i=i then continue;
      d:=r div i;
      for u:=1 to trunc(sqrt(d/2)) do
       begin
         v:=trunc(sqrt(d-u*u));
         if (u*u+v*v=d)and(gcd(u,v)=1)and(u<v)then inc(ans);
       end;
    end;
  ans:=ans*4+4;
  write(ans);
end;

begin
  init;
end.



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

历史上的今天

评论

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

页脚

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