2301: [HAOI2011]Problem b

2301: [HAOI2011]Problem b

Time Limit: 50 Sec  Memory Limit: 256 MB

Submit: 1737  Solved: 749

[Submit][Status][Discuss]

Sample Input

2 2 5 1 5 1 1 5 1 5 2

14 3

HINT

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

Source

 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];
39      for i:=1 to n do
40          begin
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;
47 end.

251 篇文章37 人订阅

0 条评论

相关文章

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

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

33350

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

35960

1257: [CQOI2007]余数之和sum

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

29880

HDU----（3294）Girls' research（manacher）

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

29450

1677: [Usaco2005 Jan]Sumsets 求和

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

31180

HUDOJ-----1394Minimum Inversion Number

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

39260