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]),那么为何不用好求的求出来然后容斥原理加加减减呢——嗯哼么么哒

 1 const maxn=150000;
 2 var
 3    i,j,k,l,m,n,x1,y1,x2,y2,z:longint;
 4    a,b:array[0..maxn] of longint;
 5 procedure swap(var x,y:longint);
 6           var z:longint;
 7           begin
 8                z:=x;x:=y;y:=z;
 9           end;
10 function doit(x,y:longint):int64;
11          var i,j,k:longint;
12          begin
13               doit:=0;
14               if x>y then swap(x,y);
15               if x=0 then exit(0);
16               i:=1;
17               while i<=x do
18                     begin
19                          if (x div (x div i))<(y div (y div i)) then
20                             k:=x div (x div i)
21                          else k:=y div (y div i);
22                          inc(doit,(b[k]-b[i-1])*int64(x div i)*int64(y div i));
23                          i:=k+1;
24                     end;
25          end;
26 begin
27      for i:=2 to maxn do
28          begin
29               if a[i]<>0 then continue;
30               for j:=i to maxn div i do a[i*j]:=i;
31          end;
32      b[1]:=1;
33      for i:=2 to maxn do
34          if a[i]=0 then b[i]:=-1 else
35             if ((i div a[i]) mod a[i])=0 then b[i]:=0 else
36                b[i]:=-b[i div a[i]];
37      for i:=2 to maxn do b[i]:=b[i]+b[i-1];
38      readln(n);
39      for i:=1 to n do
40          begin
41               readln(x1,y1,x2,y2,z);
42               x1:=(x1-1) div z;y1:=y1 div z;
43               x2:=(x2-1) div z;y2:=y2 div z;
44               writeln(doit(y1,y2)-doit(x1,y2)-doit(y1,x2)+doit(x1,x2));
45          end;
46      readln;
47 end.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

BZOJ 3211: 花神游历各国【线段树区间开方问题】

3211: 花神游历各国 Time Limit: 5 Sec  Memory Limit: 128 MB Submit: 3514  Solved: 1306...

33350
来自专栏ml

HDUOJ 2672---god is a girl 《斐波那契数》

god is a girl Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/3276...

29460
来自专栏数据结构与算法

BZOJ3560: DZY Loves Math V(欧拉函数)

$\sum_{i_1 = 0}^{b_1} \sum_{i_2 = 0}^{b_2} \dots \sum_{i_n = 0}^{b_n} \phi( p^{\...

12660
来自专栏小樱的经验随笔

HDU 1002 A + B Problem II(高精度加法(C++/Java))

A + B Problem II Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/3...

38870
来自专栏杨熹的专栏

【LEETCODE】模拟面试-134-Gas Station

新生 题目: https://leetcode.com/problems/gas-station/ There are N gas stations alon...

35960
来自专栏HansBug's Lab

1257: [CQOI2007]余数之和sum

1257: [CQOI2007]余数之和sum Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 2001  So...

29880
来自专栏ml

HDU----(3294)Girls' research(manacher)

Girls' research Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/3...

29450
来自专栏HansBug's Lab

1677: [Usaco2005 Jan]Sumsets 求和

1677: [Usaco2005 Jan]Sumsets 求和 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 6...

31180
来自专栏ml

HUDOJ-----1394Minimum Inversion Number

Minimum Inversion Number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit:...

39260
来自专栏HansBug's Lab

1441: Min

1441: Min Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 320  Solved: 213 [Submi...

22440

扫码关注云+社区

领取腾讯云代金券