HAOI2011 problem b

2301: [HAOI2011]Problem b

Time Limit: 50 Sec Memory Limit: 256 MB
Submit: 1047 Solved: 434
[Submit][Status]

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 5 1 5 1

1 5 1 5 2

Sample Output

HINT

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

题解：

其实就是容斥原理了

代码：

 uses math;

 const maxn=;

 var i,n,a,b,c,d,w,tot:longint;

     ans:int64;

     sum,mu,p:array[..maxn] of int64;

 procedure get;

  var i,j,k:longint;

      check:array[..maxn] of boolean;

  begin

  fillchar(check,sizeof(check),false);

  tot:=;mu[]:=;

  for i:= to maxn do

   begin

    if not(check[i]) then begin inc(tot);p[tot]:=i;mu[i]:=-;end;

    for j:= to tot do

     begin

      k:=i*p[j];

      if k>maxn then break;

      check[k]:=true;

      if i mod p[j]<> then mu[k]:=-mu[i]

      else begin mu[k]:=;break;end;

     end;

    end;

  for i:= to maxn do sum[i]:=sum[i-]+mu[i];

  end;

 function f(x,y:longint):int64;

  var i,last,t:longint;

  begin

  x:=x div w;y:=y div w;

  f:=;

  if x>y then begin t:=x;x:=y;y:=t;end;

  i:=;

  while i<=x do

   begin

    last:=min(x div (x div i),y div (y div i));

    inc(f,(sum[last]-sum[i-])*(x div i)*(y div i));

    i:=last+;

   end;

  exit(f);

  end;

 procedure main;

  begin

  get;

  readln(n);

  for i:= to n do

   begin

    readln(a,b,c,d,w);

    ans:=;

    inc(ans,f(b,d));

    dec(ans,f(a-,d));

    dec(ans,f(b,c-));

    inc(ans,f(a-,c-));

    writeln(ans);

   end;

  end;

 begin

  main;

 end.

不知道为什么上面的数组都要开int64才能过，我觉得不需要啊，他们存储的值都在50000以内啊……？？？？

巴特西