[BZOJ2190&BZOJ2705]欧拉函数应用两例

欧拉函数phi[n]是表示1~n中与n互质的数个数。

可以用公式phi[n]=n*(1-1/p1)*(1-1/p2)*(1-1/p3)...*(1-1/pk)来表示。（p为n的质因子）

求phi[p]的过程：

 procedure calc(p:longint;var sum:longint);

 var i:longint;

 begin

     sum:=p;

     for i:= to trunc(sqrt(p)) do

         if p mod i= then

         begin

             sum:=sum div i*(i-);

             while p mod i= do p:=p div i;

                         // 保证每次都是质因子

         end;

     if p<> then sum:=sum div p*(p-);

         // 如果p自身是质数的情况

 end;

BZOJ2190

　　直接套用即可，不处理1的情况最后加上3。需要注意的是读进来的方阵大小应该-1。

　　直接贴代码。

 program bzoj2190;

 const maxn=;

 var n,i,ans:longint;

       phi:array[-..maxn]of longint;

 procedure calc(p:longint;var sum:longint);

 var i:longint;

 begin

     sum:=p;

     for i:= to trunc(sqrt(p)) do

         if p mod i= then

         begin

             sum:=sum div i*(i-);

             while p mod i= do p:=p div i;

         end;

     if p<> then sum:=sum div p*(p-);

 end;

 begin

     readln(n);dec(n);

     for i:= to n do calc(i,phi[i]);

     ans:=;

     for i:= to n do inc(ans,phi[i]);

     if n<> then writeln(ans*+) else writeln();

 end.

BZOJ 2705

　　刚开始看可能无从下手。但是再看一眼会发现，如果枚举某个数与n的最大公约数，再求出这样的数有多少的话可能就有方法处理了。

　　我们来思考有多少个数与n的最大公约数是x，不难想出，当这个数/x，n/x的时候两数互质。也就是其个数=phi[n/x]！

　　所以只需要枚举所有的最大公约数（枚举到sqrt(n)）即可。

　　需要注意的是如果n正好是完全平方数，sqrt(n)会被计算两次。于是特判。

　　另外这道题给我们一点启发：sigma(phi[n/i])(n mod i=0)=n！

　　虽然目前还没有发现有哪里可以应用，但是式子非常优美。。>_<

 program bzoj2705;

 var i:longint;

       ans,n:int64;

 function phi(p:int64):int64;

 var i:longint;

     ans:int64;

 begin

     ans:=p;

     for i:= to trunc(sqrt(p)) do if p mod i= then

     begin

         ans:=ans*(i-) div i;

         while p mod i= do p:=p div i;

     end;

     if p<> then ans:=ans*(p-) div p;

     exit(ans);

 end;

 begin

     //sign(input,'a.in');reset(input);

     while not eof do

     begin

         readln(n);

         ans:=;

         for i:= to trunc(sqrt(n)) do if n mod i= then

         begin

             inc(ans,i*phi(n div i));

             if i*i<>n then inc(ans,(n div i)*phi(i));

         end;

         writeln(ans);

     end;

 end.

巴特西

[BZOJ2190&BZOJ2705]欧拉函数应用两例

最新文章

热门文章