高精度运算（二）
乘法与除法

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
    string s1="999999999", s2="999999999";
    vector<int> a, b;
    for(int i=s1.size()-1;i>=0;i--) a.push_back(s1[i]-'0');
    for(int i=s2.size()-1;i>=0;i--) b.push_back(s2[i]-'0');
    vector<int> c(a.size()+b.size(),0);
    for(int i=0;i<a.size();i++)
        for(int j=0;j<b.size();j++)
            c[i+j]+=a[i]*b[j];
    for(int i=0;i<c.size();i++){
        if(i+1<c.size()) c[i+1]+=c[i]/10;
        c[i]%=10;
    }
    while(c.size()>1&&c.back()==0) c.pop_back();
    for(int i=c.size()-1;i>=0;i--) cout<<c[i];
    cout<<endl;
    return 0;
}

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s; int b;
    cin >> s >> b;
    int r = 0;
    string q = "";
    for(int i=0;i<s.size();i++){
        r = r*10 + (s[i]-'0');
        q += (char)(r/b + '0');
        r = r % b;
    }
    // 去前导零
    int start = 0;
    while(start < q.size()-1 && q[start]=='0') start++;
    cout << "商: " << q.substr(start) << endl;
    cout << "余数: " << r << endl;
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
int main() {
    vector<int> a = {1};
    for(int k=2;k<=50;k++){
        int carry=0;
        for(int i=0;i<a.size()||carry;i++){
            if(i==a.size()) a.push_back(0);
            carry += a[i]*k;
            a[i] = carry%10;
            carry /= 10;
        }
    }
    for(int i=a.size()-1;i>=0;i--) cout<<a[i];
    cout<<endl;
    return 0;
}

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s; cin >> s;
    int r = 0;
    for(int i=0;i<s.size();i++)
        r = (r*10 + (s[i]-'0')) % 11;
    if(r == 0) cout << "YES" << endl;
    else cout << "余数: " << r << endl;
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
int main() {
    vector<int> a = {1};
    for(int k=0;k<100;k++){
        int carry=0;
        for(int i=0;i<a.size()||carry;i++){
            if(i==a.size()) a.push_back(0);
            carry += a[i]*2;
            a[i] = carry%10;
            carry /= 10;
        }
    }
    for(int i=a.size()-1;i>=0;i--) cout<<a[i];
    cout<<endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
    string s1, s2; cin >> s1 >> s2;
    vector<int> a, b;
    for(int i=s1.size()-1;i>=0;i--) a.push_back(s1[i]-'0');
    for(int i=s2.size()-1;i>=0;i--) b.push_back(s2[i]-'0');
    vector<int> c(a.size()+b.size(),0);
    for(int i=0;i<a.size();i++)
        for(int j=0;j<b.size();j++)
            c[i+j]+=a[i]*b[j];
    for(int i=0;i<c.size();i++){
        if(i+1<c.size()) c[i+1]+=c[i]/10;
        c[i]%=10;
    }
    while(c.size()>1&&c.back()==0) c.pop_back();
    for(int i=c.size()-1;i>=0;i--) cout<<c[i];
    cout<<endl;
    return 0;
}

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
    string s; int m;
    cin >> s >> m;
    vector<int> q;
    long long r = 0;
    for(int i=0;i<s.size();i++){
        r = r*10 + (s[i]-'0');
        q.push_back(r/m);
        r %= m;
    }
    int start=0;
    while(start<q.size()-1&&q[start]==0) start++;
    cout << "商: ";
    for(int i=start;i<q.size();i++) cout<<q[i];
    cout << endl;
    cout << "余数: " << r << endl;
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
vector<int> add(vector<int> &a, vector<int> &b) {
    vector<int> c; int carry=0;
    for(int i=0;i<a.size()||i<b.size()||carry;i++){
        int s=carry;
        if(i<a.size()) s+=a[i];
        if(i<b.size()) s+=b[i];
        c.push_back(s%10); carry=s/10;
    }
    return c;
}
int main() {
    vector<int> sum={0};
    for(int k=1;k<=10;k++){
        vector<int> p={1};
        for(int j=0;j<k;j++){
            int carry=0;
            for(int i=0;i<p.size()||carry;i++){
                if(i==p.size()) p.push_back(0);
                carry+=p[i]*k; p[i]=carry%10; carry/=10;
            }
        }
        sum=add(sum,p);
    }
    for(int i=sum.size()-1;i>=0;i--) cout<<sum[i];
    cout<<endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> mul(vector<int> &a, vector<int> &b) {
    vector<int> c(a.size()+b.size(),0);
    for(int i=0;i<a.size();i++)
        for(int j=0;j<b.size();j++)
            c[i+j]+=a[i]*b[j];
    for(int i=0;i<c.size();i++){
        if(i+1<c.size()) c[i+1]+=c[i]/10;
        c[i]%=10;
    }
    while(c.size()>1&&c.back()==0) c.pop_back();
    return c;
}

// 比较：a <= b 返回 true
bool leq(vector<int> &a, vector<int> &b) {
    if(a.size()!=b.size()) return a.size()<b.size();
    for(int i=a.size()-1;i>=0;i--)
        if(a[i]!=b[i]) return a[i]<b[i];
    return true;
}

int main() {
    string s; cin >> s;
    vector<int> n;
    for(int i=s.size()-1;i>=0;i--) n.push_back(s[i]-'0');

vector<int> lo={1}, hi;
    // hi = 10^(len/2+1)
    hi.push_back(1);
    for(int i=0;i<=s.size()/2;i++) hi.push_back(0);

vector<int> ans={1};
    while(leq(lo,hi)){
        // mid = (lo+hi)/2 用高精度除法
        // 简化：用二分逼近
        vector<int> mid = lo; // 简化实现略
        vector<int> sq = mul(mid, mid);
        if(leq(sq, n)){ ans=mid; /* lo=mid+1 */ break; }
        else { /* hi=mid-1 */ break; }
    }
    for(int i=ans.size()-1;i>=0;i--) cout<<ans[i];
    cout<<endl;
    return 0;
}