由于提高组不考
F
F
T
FFT
FFT与多项式求逆，故此处不给
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)的高精乘和高精除。
1.高精加
#include<bits/stdc++.h>
using namespace std
;
int Read(){
int x
=0,f
=1;char ch
=getchar();
while(!isdigit(ch
)){if(ch
=='-') f
=-1;ch
=getchar();}
while(isdigit(ch
)){x
=(x
<<3)+(x
<<1)+ch
-'0';ch
=getchar();}
return x
*f
;
}
char s1
[205],s2
[205];
int a
[205],b
[205],c
[205],x
=0;
int main(){
scanf("%s%s",s1
,s2
);
int n
=strlen(s1
),m
=strlen(s2
);
for(int i
=0;i
<n
;i
++) a
[n
-i
]=s1
[i
]-'0';
for(int i
=0;i
<m
;i
++) b
[m
-i
]=s2
[i
]-'0';
if(n
<m
) n
=m
;
for(int i
=1;i
<=n
;i
++){
x
=a
[i
]+b
[i
]+x
;
c
[i
]=x
%10;
x
=x
/10;
}
if(x
>0) c
[++n
]=x
;
for(int i
=n
;i
>=1;i
--) cout
<<c
[i
];
return 0;
}
2.高精减
#include<bits/stdc++.h>
using namespace std
;
int Read(){
int x
=0,f
=1;char ch
=getchar();
while(!isdigit(ch
)){if(ch
=='-') f
=-1;ch
=getchar();}
while(isdigit(ch
)){x
=(x
<<3)+(x
<<1)+ch
-'0';ch
=getchar();}
return x
*f
;
}
char s1
[205],s2
[205];
int a
[205],b
[205],c
[205];
int main(){
scanf("%s%s",s1
,s2
);
int n
=strlen(s1
),m
=strlen(s2
);
for(int i
=0;i
<n
;i
++) a
[n
-i
]=s1
[i
]-'0';
for(int i
=0;i
<m
;i
++) b
[m
-i
]=s2
[i
]-'0';
if(n
<m
||n
==m
&&strcmp(s1
,s2
)<0){
printf("-");
for(int i
=1;i
<=m
;i
++) swap(a
[i
],b
[i
]);
swap(n
,m
);
}
for(int i
=1;i
<=n
;i
++){
int x
=10+a
[i
]-b
[i
];
c
[i
]=x
%10;
a
[i
+1]=a
[i
+1]+x
/10-1;
}
while(n
>1&&c
[n
]==0) n
--;
for(int i
=n
;i
>=1;i
--) cout
<<c
[i
];
return 0;
}
3.高精乘（
O
(
n
2
)
O(n^2)
O(n2)）
#include<bits/stdc++.h>
using namespace std
;
int Read(){
int x
=0,f
=1;char ch
=getchar();
while(!isdigit(ch
)){if(ch
=='-') f
=-1;ch
=getchar();}
while(isdigit(ch
)){x
=(x
<<3)+(x
<<1)+ch
-'0';ch
=getchar();}
return x
*f
;
}
char s1
[205],s2
[205];
int a
[205],b
[205],c
[505];
int main(){
scanf("%s%s",s1
,s2
);
int n
=strlen(s1
),m
=strlen(s2
);
for(int i
=0;i
<n
;i
++) a
[n
-i
]=s1
[i
]-'0';
for(int i
=0;i
<m
;i
++) b
[m
-i
]=s2
[i
]-'0';
for(int i
=1;i
<=n
;i
++){
int x
=0;
for(int j
=1;j
<=m
;j
++){
x
=x
+a
[i
]*b
[j
]+c
[i
+j
-1];
c
[i
+j
-1]=x
%10;
x
=x
/10;
}
c
[i
+m
]=c
[i
+m
]+x
;
}
int len
=n
+m
;
while(len
>1&&c
[len
]==0) len
--;
for(int i
=len
;i
>=1;i
--) cout
<<c
[i
];
return 0;
}
4.高精除低精
#include<bits/stdc++.h>
using namespace std
;
int Read(){
int x
=0,f
=1;char ch
=getchar();
while(!isdigit(ch
)){if(ch
=='-') f
=-1;ch
=getchar();}
while(isdigit(ch
)){x
=(x
<<3)+(x
<<1)+ch
-'0';ch
=getchar();}
return x
*f
;
}
char s1
[205];
int a
[205],b
,c
[205];
int main(){
scanf("%s",s1
);
b
=Read();
int n
=strlen(s1
);
for(int i
=0;i
<n
;i
++) a
[i
]=s1
[i
]-'0';
int x
=0;
for(int i
=0;i
<n
;i
++){
c
[i
]=(x
*10+a
[i
])/b
;
x
=(x
*10+a
[i
])%b
;
}
int pos
=1;
while(c
[pos
]==0&&(pos
<n
-1)) pos
++;
for(int i
=pos
;i
<n
;i
++) cout
<<c
[i
];
cout
<<endl
<<x
;
return 0;
}
5.高精除高精（
O
(
n
2
)
O(n^2)
O(n2)）
#include<bits/stdc++.h>
using namespace std
;
int Read(){
int x
=0,f
=1;char ch
=getchar();
while(!isdigit(ch
)){if(ch
=='-') f
=-1;ch
=getchar();}
while(isdigit(ch
)){x
=(x
<<3)+(x
<<1)+ch
-'0';ch
=getchar();}
return x
*f
;
}
char s1
[205],s2
[205];
int a
[205],b
[205],c
[205],hi
,n
,m
;
bool comp(int lw
){
if(hi
-lw
>m
) return true;
if(hi
-lw
<m
) return false;
int tmp
=m
;
while(tmp
>0&&a
[lw
+tmp
]==b
[tmp
]) tmp
--;
if(tmp
==0) return true;
if(a
[lw
+tmp
]>b
[tmp
]) return true;
return false;
}
void highminus(int lw
){
int x
=0;
for(int i
=1;i
<=m
;i
++){
x
=10+a
[lw
+i
]-b
[i
];
a
[lw
+i
]=x
%10;
a
[lw
+i
+1]=a
[lw
+i
+1]-1+x
/10;
}
while(hi
>lw
&&a
[hi
]==0) hi
--;
}
int main(){
scanf("%s%s",s1
,s2
);
n
=strlen(s1
),m
=strlen(s2
);
for(int i
=0;i
<n
;i
++) a
[n
-i
]=s1
[i
]-'0';
for(int i
=0;i
<m
;i
++) b
[m
-i
]=s2
[i
]-'0';
hi
=n
;
for(int i
=n
;i
>0;i
--){
while(comp(i
-1)){
c
[i
]++;
highminus(i
-1);
}
}
while(n
>0&&c
[n
]==0) n
--;
for(int i
=n
;i
>0;i
--) cout
<<c
[i
];
cout
<<endl
;
while(m
>0&&a
[m
]==0) m
--;
for(int i
=m
;i
>0;i
--) cout
<<a
[i
];
return 0;
}
