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∗x3+2∗x2+3∗x+4 và Q(x)=5x+6 sau đó nhân 2 đa thức với nhau ta được (P∗Q)(x)=5∗x4+16x3+27x2+38x+24

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

1234∗56=5∗104+16∗103+27∗102+38∗10+24=4+2∗10+38∗10+27∗102+16∗103+5∗104=...=

=4+0∗10+1∗102+9∗103+6∗104=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

Copy
1234
56

Output

Copy
69104
tichpx

Comments


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

    code tham khảo

    Copy
    #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;

}