AcWing 794. 高精度除法
原题链接
简单
作者:
杰森
,
2024-12-20 18:06:51
,
所有人可见
,
阅读 2
import java.util.Scanner;
public class Main {
public static String highPerSub(String a,String b){
int flag = 0;
StringBuilder re = new StringBuilder("");
String a1,b1;
if((a.length() > b.length()) || (a.length() == b.length() && a.compareTo(b) > 0)){
a1 = a;b1 = b;
}
else if(a.compareTo(b) == 0){
re.append(0);
return re.toString();
}
else{
a1 = b;b1 = a;flag = 1;
}
//a1 >b1
int la = a1.length()-1,lb = b1.length()-1,c = 0;
while(la >=0 || lb >= 0 || c >0){
int t = 0;
if(la >= 0) t += a1.charAt(la--)-'0';
if(lb >= 0) t -= b1.charAt(lb--)-'0';
if(c > 0) t -= c;
if(t >= 0){re.append(t);c = 0;}
else{re.append(10+t);c = 1;}
}
int i = re.length()-1;
while(re.charAt(i) == '0'){i--;};
re.delete(i+1,re.length());
if(flag != 0)re.append('-');
re.reverse();
return re.toString();
}
public static String highPerMul(String a,String b){
if(a.equals("0") || b.equals("0")){return "0";}
int la = a.length(),lb = b.length();
int[] mu = new int[la+lb+2];
int fur = -1;
for(int i = lb-1; i >= 0; i--){
for(int j = la-1; j >= 0; j--){
int p =la+lb-i-j-2;
int r = (a.charAt(j)-'0')*(b.charAt(i)-'0');
mu[p] += r;
fur = Math.max(fur,p);
}
}
for(int i = 0 ; i <= fur;i++){
int num = mu[i] % 10;
int c = mu[i]/10;
mu[i] = num;
if(c != 0){
fur = Math.max(fur,i+1);
mu[i+1] += c;
}
}
StringBuilder sb = new StringBuilder("");
for(int i = fur; i>=0;i--){
sb.append(mu[i]);
}
return sb.toString();
}
public static String highPerAdd(String a,String b){
int la = a.length()-1;
int lb = b.length()-1;
StringBuilder res = new StringBuilder("");
int c = 0;
while(la >= 0 || lb >= 0 || c !=0){
int t = 0;
if(la >= 0)t += a.charAt(la--)-'0';
if(lb >= 0)t += b.charAt(lb--)-'0';
if(c != 0)t += c;
res.append(t % 10);
c = t / 10;
}
res.reverse();
return res.toString();
}
public static void highPerDiv(String a,String b){
int la = a.length(),lb = b.length();
if(a.equals("0")) {System.out.println("0\n0");return;}
if(la < lb || (la == lb && a.compareTo(b) < 0)) {System.out.println("0\n"+a);return;}
int flag = 0;
int p = 0;
StringBuilder divNum = new StringBuilder("");
String temp = new String("0");
for(int i = 0; i < la;i++){
temp = highPerAdd(highPerMul(temp,"10"),String.valueOf(a.charAt(i)-'0'));
String r = new String(highPerSub(temp,b));
int count = 0;
while(r.charAt(0) !='-'){
count++;
temp = new String(r);
r = new String(highPerSub(temp,b));
}
if(count != 0){flag = 1;}
if(flag == 1){divNum.append(count);}
}
System.out.println(divNum.toString());
System.out.println(temp);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String a = scanner.next(),b = scanner.next();
highPerDiv(a,b);
}
}