Nhân 2 số lớn

Submit solution
Points: 2 (partial)
Time limit: 1.0s
Memory limit: 98M
Author:
TICHPX
Problem type
Allowed languages
C, C++, C11, CLANG, CLANGX, DART, F95, GAS32, Itercal, java, kotlin, LEAN, LISP, MONOVB, PIKE, prolog, RUST, SWIFT, TUR, V8JS, VB, ZIG

Bài toán về nhân 2 số lớn chỉ được dùng ngôn ngữ lập trình C/C++

Khi giảng dạy về lập trình nhân 2 đa thức thầy Tichpx lấy ví dụ muốn nhân 2 số nguyên dương với nhau ta biểu diễn nó dưới dạng 1 đa thức có biến là 10 và nhân 2 đa thức với nhau rồi đưa về đa thức mới có biến là 10 lấy các hệ số là xong

Ví dụ muốn nhân \(1234*56\) thì ta xét \(P(x) = 1*x^3+2*x^2+3*x+4\) và \(Q(x)= 5x+6\) sau đó nhân 2 đa thức với nhau ta được \((P*Q)(x) = 5*x^4+16x^3+27x^2+38x+24\)

Sau đó ta thay \(x=10\) vào ta được

\( 1234*56 = 5*10^4+16*10^3+27*10^2+38*10+24 = 4+2*10 + 38*10+ 27*10^2+ 16*10^3 +5*10^4 = ... =\)

\( = 4+0*10 +1*10^2 + 9*10^3 +6*10^4 = 69104\)

Toto đã áp dụng được cách này để nhân 2 số lớn nhưng để đẩy nhanh thuật toán Toto đã cải tiến không phải là x=10 mà biểu diễn qua đa thức với x=1000 bạn hãy giúp Toto nhé

Input

Hai dòng mỗi dòng chứa một số nguyên dương không vượt quá 100 chữ số

Output

Tích của hai số

Yêu cầu : chỉ được dùng ngôn ngữ lập trình C/C++

Ví dụ

Input

1234
56

Output

69104
tichpx

Comments


  • 1
    TICHPX  commented on July 18, 2020, 6:07 a.m.

    code tham khảo

    #include"bits/stdc++.h"
using namespace std;

int main()
{
    string x,y;
    vector<long long> P,Q,R;
    cin>>x; reverse(x.begin(),x.end()); for(char z:x) P.push_back(z-'0');
    cin>>x; reverse(x.begin(),x.end()); for(char z:x) Q.push_back(z-'0');
    R.resize(P.size()+Q.size()-1);
    for(int i=0;i<P.size();i++)
    for(int j=0;j<Q.size();j++) R[i+j]+=P[i]*Q[j];
    long long t=0;
    for(auto &z:R){t=t+z; z=t%10;t=t/10;}
    while(t){R.push_back(t%10);t/=10;}
    for(auto z=R.rbegin();z!=R.rend();z++) cout<<*z;

}