[BZOJ2440]完全平方数解题报告|莫比乌斯函数的应用

完全平方数

　　小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。
　　这天是小X的生日，小 W 想送一个数给他作为生日礼物。当然他不能送一个小X讨厌的数。他列出了所有小X不讨厌的数，然后选取了第 K个数送给了小X。小X很开心地收下了。
　　然而现在小 W 却记不起送给小X的是哪个数了。你能帮他一下吗？

　　还记得第一次接触这道题是一年前吧..那时候参加了一场某OJ的比赛

　　然后并不会做..在discuss里面发现是“BZOJ2440原题”

　　然后看到了一个叫做莫比乌斯函数的东西...很努力地看但是仍然没看懂...

　　也奇怪..现在就能看懂了呢...

　　莫比乌斯函数：

　　μ（1）=1；

　　对于每个质因子的次数都为1的数n,假设其能拆分出k个质因子，μ(n)=（-1）^k

　　其他情况下μ（n）=0

　　构造方法：

　　首先容易证明莫比乌斯函数是积性函数

　　然后用线筛

procedure build;

var m:int64;

    i,j:longint;

begin

    fillchar(vis,sizeof(vis),true);

    prime[]:=;

    m:=trunc(sqrt(INF));mu[]:=;

    for i:= to m do

    begin

        if vis[i] then

        begin

            inc(prime[]);

            prime[prime[]]:=i;

            mu[i]:=-;

        end;

        for j:= to prime[] do

        begin

            if i*prime[j]>m then break;

            vis[i*prime[j]]:=false;

            if i mod prime[j]= then

            begin

                mu[prime[j]*i]:=;

                break;

            end;

            mu[prime[j]*i]:=-mu[i];

        end;

    end;

end;

　　对于这道题，很容易想到二分答案+容斥

　　然后发现由偶数个次数为一的质数乘起来的完全平方因子，对答案的贡献是正的，奇数个是负的

　　这个就可以用莫比乌斯函数来替代

 program bzoj2440;

 const INF = ;maxn = ;

 var test,L,R,ans,k,mid:int64;

     tt:longint;

     prime,mu:array[-..maxn]of int64;

     vis:array[-..maxn]of boolean;

 procedure build;

 var m:int64;

     i,j:longint;

 begin

     fillchar(vis,sizeof(vis),true);

     prime[]:=;

     m:=trunc(sqrt(INF));mu[]:=;

     for i:= to m do

     begin

         if vis[i] then

         begin

             inc(prime[]);

             prime[prime[]]:=i;

             mu[i]:=-;

         end;

         for j:= to prime[] do

         begin

             if i*prime[j]>m then break;

             vis[i*prime[j]]:=false;

             if i mod prime[j]= then

             begin

                 mu[prime[j]*i]:=;

                 break;

             end;

             mu[prime[j]*i]:=-mu[i];

         end;

     end;

 end;

 function solve(x:int64):int64;

 var sum:int64;

     i:longint;

 begin

     sum:=;

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

             inc(sum,(x div (int64(i)*i))*mu[i]);

     exit(sum);

 end;

 begin

     assign(input,'bzoj2440.in');reset(input);

     readln(test);

     build;

         for tt:= to test do

     begin

         readln(k);

         L:=;R:=INF;ans:=-;

         while L<=R do

         begin

             mid:=(L+R) >> ;

             if solve(mid)>=k then

             begin

                 ans:=mid;R:=mid-;

             end else L:=mid+;

         end;

         writeln(ans);

     end;

 end.

巴特西

[BZOJ2440]完全平方数解题报告|莫比乌斯函数的应用

最新文章

热门文章