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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Bzoj2818】【Gcd】  

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

  下载LOFTER 我的照片书  |
   题目大意:给定整数N,求1~N里面的数对x,y满足gcd(x,y)为素数的数对的个数。

   0.0...其实考虑每一个素数p,咱们的x,y的gcd(x,y)=p,则gcd(x/p,y/p)=1,而x/p,y/p的范围是在n/p内的,这个就转化成了在n/p内互质的数的个数。
   然后关于 求 1~n里面互质的有序数对 的个数..
   0.0咱不会... 问了一下数学帝 sharkfly君,然后就被虐了= =。

   其实就是一个裸的定义了啊啊啊啊啊啊啊...即欧拉函数。
   好久没看这玩意了...完全忘记了= =

   欧拉函数的定义:phi(n)表示1~n内与n互质的数的个数。
   所以最后的答案显然是∑phi[i]*2-1(去掉[1,1]这个数对一次,它被计算了两次)

   然后就是关于求欧拉函数phi,这个是有线性方法求所有的phi[1]~phi[n]。

   不过为了能够在以后也能够利用欧拉函数,咱们可以尝试用证明来理解它。
   首先咱们可以来证明一下一个性质:phi[n]=n*(1-1/pi) pi是n的所有质因数。

   step1:首先咱们可以知道,对于质数,phi[n]=n-1,这个是非常显然的额。

   step2:然后咱们来证明一个结论,即phi是积性函数,若有 n=a*b,a,b互质,则phi[n]=phi[a]*phi[b]。
   这个的证明需要运用到中国剩余定理,咱们实际上可以发现,互质的数的集合实际上可以看做乘法模的生成群,咱们把a和b两个生成群任取两个元素i,j相乘得到一个新的元素x.
    考虑中国剩余定理【算导上的】:
    令n=n1*n2*n3..*nk,其中因子两两互质。则有以下对应关系:
    a<->(a1,a2,...ak)
    其中a是某数模n意义下的余数,ai是某数模ni意义下的余数,即某数模n的余数等价于该数模ni的余数,两者可以相互转化的。
    然后考虑咱们这里的结论,ab互质,则phi[n]=phi[a]*phi[b],咱们考虑从phi[a]和phi[b]任意选择两个元素i,j,咱们只要证明 i*j是有唯一的解i与j的,不存在其他的解u,v,其中u∈phi[a],v∈phi[b],咱们证明这个结论,可以直接运用到中国剩余定理,即 咱们知道了 i*j mod n意义下的余数是i*j,那么在a,b意义下i,j是唯一的!!!
    所以咱们证明了随便选择一个i∈phi[a],j∈phi[b]的话,i*j都是唯一的,所以phi[n]的元素的个数就phi[a]*phi[b]。

    step3:咱们证明 若p是质数,那么 phi(p^k)=p^k-p^(k-1)(k∈正整数)
    这个实际上考虑一下意义即可,p^k内只要不包含因数p的数都与它互质,补集思想,咱们只要计算出包含质数p的数有多少个即可,而这个显然就是 p^(k-1)个,那么个数就是 p^k-p^(k-1)=p^k(1-1/p)
   
    step4:证明最终结论。
    n=p1^k1*p2^k2*...*pi^ki
    由于step2 的结论,phi[n]=phi[p1^k1]*phi[p2^k2]*...*phi[pi^ki]=p1^k1(1-1/p1)....pi^ki*(1-1/pi)=
   n*(1-1/p1)(1-1/p2)...(1-1/pi)

    不过用这个求phi(1)~phi(n),复杂度略高..,咱们其实有线性求phi的方法,那就是在线性筛法的基础上求的。
    线性筛法的时候,扫描到每一个数,如果这个数是质数,则phi(i)=i-1,
    然后对于合数x,咱们知道可以在之前某个数y的时候用 某个质数p*y给排除掉,如果y mod p!=0的话,显然它们是互质的,由积性函数的性质,咱们有 phi[x]=phi[y]*phi[p],否则它们不是互质的,根据定义,咱们实际上可以设 y=p^k*w,那么可以变成 phi[y]=phi[w]*phi[p^k]=phi[w]*(p^k-p^(k-1)),而phi[x]=phi[w]*phi[p^(k+1)]=
phi[w]*(p^(k+1)-p^k)=p*phi[w]*(p^k-p^(k-1))=p*phi[y]。
   整理一下,若x是合数,那么它之前有 y*p=x,咱们分类:
   若y mod p!=0,则 phi(x)=phi(y)*phi(p) ,否则 phi(x)=phi(y)*p。

   现在咱们线性得出了这个phi[],然后咱们从大到小再枚举因数,对于剩下的n求出1+∑phi[k]*2(1<k<=n)即可,这样子复杂度也是O(N)的,就可以AC这道题了。

=======================

program bzoj2818;
const maxn=10000010;
      maxm=10000010;
var v:array[0..maxn]of boolean;
    phi:array[0..maxn]of longint;
    p:array[0..maxm]of longint;
    n:longint;
    ans,tmp:int64;

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,j,k,ed:longint;
begin
  read(n);
  prepare;
  ed:=2;tmp:=1;ans:=0;
  for i:=p[0] downto 1 do
   begin
     j:=n div p[i];
     for k:=ed to j do
      tmp:=tmp+(phi[k]*2);
     ed:=j+1;
     ans:=ans+tmp;
   end;
  write(ans);
end;

begin
  init;
end.





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

历史上的今天

评论

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

页脚

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