高精度不会的迅速暴击此处

Posted by Cww97 on 2016-01-07

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/50474854
Rectangle 数矩形
这注定是个不眠之夜!
因为MSH 达到了RPK 的要求,所以RPK 给了MSH 第二个惊喜。RPK 把
MSH 带到了一个硕大而神秘的广场,如此广阔的空间只有两个人,而一切静匿到足以听见对方的心跳。
MSH 沉醉了。
RPK:“你知道我有多少话想跟你说么?”
MSH 摇了摇头。
RPK:“你可以数出来啊,在这个广场上的地面上你能数到矩形的数量,就是我想说的话的数量。”
MSH 数了数,实在是太多了,她完全数不尽。
整个广场的地面由两个行和列分别为N1,M1 和N2,M2 的矩形组成,这两个矩形交叉成十字(N1<N2,M1>M2),在这个图形中,一共有多少个矩形呢?

这里写图片描述
这里写图片描述

Input
一共四行,每行一个数,分别表示N1,M1 和N2,M2。
Output
一个数表示矩形的数量
Sample Input
7
9
10
6

Sample Output
1827

数据规模:
20%的数据每个数≤100;
40%的数据每个数≤10000;
100%的数据每个数≤10的99次方;

【题解】f(x,y)表示x行y列内有多少个矩形,显然f(x,y)=(x*(x+1)/2)_(y_(y+1)/2)
输出f(n1,m1)+f(n2,m2)-f(n1,m2)
数字大的丧心病狂,高精度啦

【code】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
 program cx;
type bignum=array[0..1000]of longint;
var i:longint;
a,b,c,d,f1,f2,f3,ans:bignum;
st:string;

function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end;

function plus1(x:bignum):bignum;
var i:longint;
begin
x[1]:=x[1]+1;
for i:=1 to a[0] do
begin
if x[i]<10 then break;
x[i+1]:=x[i+1]+x[i] div 10;
x[i]:=x[i] mod 10;
end;
if x[x[0]+1]>0 then inc(x[0]);
exit(x);
end;

function plus(a,b:bignum):bignum;
var c:bignum;
i,x:longint;
begin
fillchar(c,sizeof(c),0);
c[0]:=max(a[0],b[0]);
for i:=1 to c[0] do
begin
x:=a[i]+b[i];
c[i]:=c[i]+x mod 10;
c[i+1]:=c[i+1]+x div 10;
end;
if c[c[0]+1]>0 then inc(c[0]);
exit(c);
end;

function minus(a,b:bignum):bignum;
var c:bignum;
x,i:longint;
begin
x:=0;
fillchar(c,sizeof(c),0);
c[0]:=a[0];
for i:=1 to c[0] do
begin
dec(a[i+1]);
x:=x+a[i]-b[i]+10;
c[i]:=x mod 10;
x:=x div 10;
end;
while (c[c[0]]=0)and(c[0]>1) do dec(c[0]);
exit(c);
end;

function mul(a,b:bignum):bignum;
var c:bignum;
i,x,j:longint;
begin
fillchar(c,sizeof(c),0);
c[0]:=a[0]+b[0];
for i:=1 to a[0] do
for j:=1 to b[0] do
begin
c[i+j-1]:=c[i+j-1]+a[i]*b[j];
c[i+j]:=c[i+j]+c[i+j-1]div 10;
c[i+j-1]:=c[i+j-1]mod 10;
end;
while (c[c[0]]=0)and(c[0]>1) do dec(c[0]);
exit(c);
end;

function chu4(a:bignum):bignum;
var i,x:longint;
b:bignum;
begin
x:=0;
fillchar(b,sizeof(b),0);
for i:=a[0] downto 1 do
begin
x:=x*10+a[i];
b[i]:=x div 4;
x:=x mod 4;
end;
b[0]:=a[0];
while (b[b[0]]=0) and (b[0]>1) do dec(b[0]);
exit(b);
end;

begin
assign(input, 'rectangle.in'); reset(input);
//assign(output,'rectangle.out');rewrite(output);
readln(st); a[0]:=length(st);
for i:=1 to a[0] do val(st[i],a[a[0]-i+1]);
readln(st); b[0]:=length(st);
for i:=1 to b[0] do val(st[i],b[b[0]-i+1]);
readln(st); c[0]:=length(st);
for i:=1 to c[0] do val(st[i],c[c[0]-i+1]);
readln(st); d[0]:=length(st);
for i:=1 to d[0] do val(st[i],d[d[0]-i+1]);

f1:=chu4(mul(mul(a,b),mul(plus1(a),plus1(b))));
f2:=chu4(mul(mul(c,d),mul(plus1(c),plus1(d))));
f3:=chu4(mul(mul(a,d),mul(plus1(a),plus1(d))));
ans:=minus(plus(f1,f2),f3);
for i:=ans[0] downto 1 do write(ans[i]);
writeln;
close(input);
//close(output);
end.