2301: [HAOI2011]Problem b

2301: [HAOI2011]Problem b

Time Limit: 50 Sec  Memory Limit: 256 MB
Submit: 1737  Solved: 749
[ Submit][ Status][ Discuss]

Description

 

对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。

Input

第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、k

 

Output

共n行，每行一个整数表示满足要求的数对(x,y)的个数

 

Sample Input

2

2 5 1 5 1

1 5 1 5 2

Sample Output

14

3

HINT

 

100%的数据满足：1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000

 

Source

 

题解：一个霸(dou)气(bi)的莫比乌斯反演，然后没啥了，开始瞎搞——不过这题里面有个重要的思想——既然直接求某“悬空”区间的结果（“悬空”区间即像本题中第一个值设定为[a,b]，而不是(0,b]），那么为何不用好求的求出来然后容斥原理加加减减呢——嗯哼么么哒

const maxn=150000;
var
   i,j,k,l,m,n,x1,y1,x2,y2,z:longint;
   a,b:array[0..maxn] of longint;
procedure swap(var x,y:longint);
          var z:longint;
          begin
               z:=x;x:=y;y:=z;
          end;
function doit(x,y:longint):int64;
         var i,j,k:longint;
         begin
              doit:=0;
              if x>y then swap(x,y);
              if x=0 then exit(0);
              i:=1;
              while i<=x do
                    begin
                         if (x div (x div i))<(y div (y div i)) then
                            k:=x div (x div i)
                         else k:=y div (y div i);
                         inc(doit,(b[k]-b[i-1])*int64(x div i)*int64(y div i));
                         i:=k+1;
                    end;
         end;
begin
     for i:=2 to maxn do
         begin
              if a[i]<>0 then continue;
              for j:=i to maxn div i do a[i*j]:=i;
         end;
     b[1]:=1;
     for i:=2 to maxn do
         if a[i]=0 then b[i]:=-1 else
            if ((i div a[i]) mod a[i])=0 then b[i]:=0 else
               b[i]:=-b[i div a[i]];
     for i:=2 to maxn do b[i]:=b[i]+b[i-1];
     readln(n);
     for i:=1 to n do
         begin
              readln(x1,y1,x2,y2,z);
              x1:=(x1-1) div z;y1:=y1 div z;
              x2:=(x2-1) div z;y2:=y2 div z;
              writeln(doit(y1,y2)-doit(x1,y2)-doit(y1,x2)+doit(x1,x2));
         end;
     readln;
end.