首页 > 其他 > 详细

bzoj 2749 杂题

时间:2014-07-22 23:16:05      阅读:461      评论:0      收藏:0      [点我收藏+]

  我们可以发现,phi(x)与x相比,相当于x的每个质因子-1后再分解质因数,添加到现有的质因子中,比如质因子13相当于将13变成12,然后分解成2*2*3,再将2的质数+2,3的指数+1,除了质因子2之外的所有质因子都满足这一性质,每次有一个质因子2相当于变成1,也就是没有了。那么我们可以将问题转化成一个大数,每个质因子分解到最后会分成多少个2,比如刚才的13,变成2*2*3,然后3变成2,那么13求phi到最后就是3个2,也就是消掉一个13需要求3次phi,如果我们可以处理出每个质数最后分解成多少个2,就可以解决问题。

  求分解多少个2可以线性筛的时候处理,设w[i]代表i这个数分解成多少个2,那么如果i为质数,w[i]=w[i-1],否则w[i*prime[j]]=w[prime[j]]+w[i]。开始现将w[2]设为1.

  还有就是如果开始的大数是奇数的时候,我们需要将答案加1,因为第一次求phi不会有2这一项被消掉,第二次开始才会不断地消2,每个质数分解之后-1,一定会是偶数,所以每次都能产生至少一个新的2的质因子,这样就保证了这个算法的正确性。

bubuko.com,布布扣
/**************************************************************
    Problem: 2749
    User: BLADEVIL
    Language: Pascal
    Result: Accepted
    Time:456 ms
    Memory:1104 kb
****************************************************************/
 
//By BLADEVIL
var
    prime, w                    :array[0..100010] of longint;
    flag                        :array[0..100010] of boolean;
 
procedure make;
var
    i, j                        :longint;
begin
    for i:=2 to 100000 do
    begin
        if not flag[i] then
        begin
            inc(prime[0]);
            prime[prime[0]]:=i;
            w[i]:=w[i-1];
            if i=2 then w[i]:=1;
        end;
        for j:=1 to prime[0] do
        begin
            if prime[j]*i>100000 then break;
            w[prime[j]*i]:=w[i]+w[prime[j]];
            flag[prime[j]*i]:=true;
            if i mod prime[j]=0 then break;
        end;
    end;
end;
 
procedure main;
var
    i, j, k                     :longint;
    t                           :longint;
    n                           :longint;
    ans                         :int64;
    x, y                        :longint;
    f                           :boolean;
begin
    read(t);
    for k:=1 to t do
    begin
        read(n);
        ans:=0; f:=false;
        for i:=1 to n do
        begin
            read(x,y);
            if x=2 then f:=true;
            ans:=ans+int64(w[x])*int64(y);
        end;
        if not f then ans:=ans+1;
        writeln(ans);
    end;
end;
     
 
begin
    make;
    main;
end.
bubuko.com,布布扣

bzoj 2749 杂题

原文:http://www.cnblogs.com/BLADEVIL/p/3514181.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!