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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Bzoj2190】【SDOI2008】【仗仪队】  

2014-04-29 19:43:38|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    题目大意:n*n个点的点阵,左下角为(0,0),右上角为(n-1,n-1),求从左下角[0,0]能看到的人数。
    CF某一道题的即视感【传送门】【那道题是这道题的一个非常大的扩展】...那个是求所有点能够看到的人数的和,这个是求左下角能看到的人数,不过觉得思想应该差不多额0.0咱们实际上就需要枚举一个向量,[a,b]表示从[0,0]到[a,b]的一个向量,而[a,b]能被[0,0]看到当且仅当a,b互质[假设不互质的话,会有一个更小的平行向量],所以实际上这道题就是求 n-1 内 互质数对的个数0.0
    这个的求法可以O(N)用欧拉函数求,详细的证明见咱的bzoj2818的题解【题解君
    0.0然后就没了额...

    ps:这道题的数据貌似没有考虑n=1的情况额...
=========================

program bzoj2190;
const maxn=40010;
var v:array[0..maxn]of boolean;
    p,phi:array[0..maxn]of longint;
    ans:int64;
    n:longint;

procedure prepare;
var i,j:longint;
begin
  fillchar(v,sizeof(v),true);
  p[0]:=0;
  for i:=2 to n do
   begin
     if v[i] then
      begin
        inc(p[0]);
        p[p[0]]:=i;
        phi[i]:=i-1;
      end;
     for j:=1 to p[0] do
      begin
        if (i*p[j]<=n)then v[i*p[j]]:=false;
        if i*p[j]>n then break;
        if i mod p[j]=0 then
          begin
            phi[i*p[j]]:=phi[i]*p[j];
            break;
          end
        else phi[i*p[j]]:=phi[i]*phi[p[j]];
      end;
   end;
end;

procedure init;
var i:longint;
begin
  read(n);dec(n);
  prepare;
  ans:=3;
  for i:=2 to n do
   ans:=ans+phi[i]*2;
  write(ans);
end;

begin
  init;
end.





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

历史上的今天

评论

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

页脚

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