C語言實作 藍橋杯 算法提高 高精度乘法

試題 算法提高 高精度乘法

                                                                                  藍橋杯試題解答彙總連結

資源限制

       時間限制：1.0s 記憶體限制：256.0MB

問題描述

       計算機真是最傻的東西；他都不能計算大于10^65-1的a*b，請你幫這個“最傻”的東西過關，否則它就真的隻認識1和0了。

輸入格式

       共兩行；第一行輸入一個整數a；第一行輸入一個整數b。

輸出格式

       共一行，一個表示a*b的整數。

樣例輸入

2147483647
2147483647
           

樣例輸出

4611686014132420609
           

資料規模與約定

10^65-1<a,b<10^201-1
           

代碼

#include <stdio.h>
#include <string.h>
int main() {
	char num1[210], num2[210];// 每個數最長200位注意開的數組大小
	scanf("%s\n%s",num1,num2);
	int num[400] = {0}, i, j;// 因為是兩個數相乘是以結果最大可能為400位 
	int len1 = strlen(num1), len2 = strlen(num2), ca, len; 
	len = len1+len2;// len1、len2分别代表num1、num2的長度 
	for(i = len2-1;i >= 0; --i) {
		ca = 0;// ca代表進位 
		for(j = len1-1;j >= 0; --j) {
			num[i+j+1] += (num1[j]-'0')*(num2[i]-'0');// 模拟手算相乘 
			ca = num[i+j+1]/10;// 求出進位 
			num[i+j+1] %= 10;// 保留本位的數字 
			num[i+j] += ca;// 向前進位 
		}
	}
	int f = 0;
	for(i = 0;i < len; ++i) {
		if(num[i]) {// 排除開頭的0 
			f = 1;
		}
		if(f) {
			printf("%d",num[i]);
		}
	}
	return 0;
}