15

tttnns LV 7 @ 2017-03-11 20:31:51

朴素n2+FFT智能切换，完整高精度类
长代码预警

#include <string>
#include <sstream>
#include <map>
#include <cmath>
#include <cstdio>
// included bigint.h
#ifndef DODECAHEDRON_BIGINT_H_
#define DODECAHEDRON_BIGINT_H_

#include <vector>
#include <iostream>
#include <map>
#include <stdexcept>
#include <string>

namespace Dodecahedron
{
class __fft;
class Bigint
{
public:
    class arithmetic_error : public std::runtime_error
    {
    public:
        explicit arithmetic_error(const std::string& what_arg)
            : std::runtime_error(what_arg) {}
    };
    friend class __fft;

private:
    std::vector<int> number;
    // don't modify this directly through const. use flip_positive
    mutable bool positive;
    static const int default_base=100000000;
    static const int default_digits_per_element=8;

public:
    //Constructors
    Bigint();
    Bigint(long long);
    Bigint(std::string);
    Bigint(const Bigint& b);

    //Adding
    Bigint operator+(Bigint const &) const;
    Bigint &operator+=(Bigint const &);

    //Subtraction
    Bigint operator-(Bigint const &) const;
    Bigint &operator-=(Bigint const &);

    //Multiplication
    Bigint operator*(Bigint const &) const;
    Bigint &operator*=(Bigint const &);
    bool force_fft;

    //Division & modulo operation
    Bigint operator/(Bigint const&) const;
    Bigint &operator/=(Bigint const &);
    Bigint operator%(Bigint const&) const;
    Bigint &operator%=(Bigint const &);
    friend Bigint sub_number(Bigint &p, Bigint &q);
    friend void divide(Bigint p, Bigint q, std::vector<Bigint>&);

    //Compare
    bool operator<(const Bigint &) const;
    bool operator>(const Bigint &) const;
    bool operator<=(const Bigint &) const;
    bool operator>=(const Bigint &) const;
    bool operator==(const Bigint &) const;
    bool operator!=(const Bigint &) const;

    //Allocation
    Bigint operator=(const long long &);

    //Input&Output
    friend std::istream &operator>>(std::istream &, Bigint &);
    friend std::ostream &operator<<(std::ostream &, Bigint const &);

    //Helpers
    void clear();
    Bigint &abs();

    //Power
    Bigint &pow(int const &);

    //Trivia
    int digits() const;
    int trailing_zeros() const;
private:
    int segment_length(int) const;
    Bigint pow(int const &, std::map<int, Bigint> &);
    int compare(Bigint const &) const; //0 a == b, -1 a < b, 1 a > b
    void flip_positive() const;
    void delete_precode_zero();
};

Bigint abs(Bigint);
std::string to_string(Bigint const &);
Bigint factorial(int);
}

#endif

#ifndef DODECAHEDRON_FFT_H_
#define DODECAHEDRON_FFT_H_
namespace Dodecahedron
{
void __fft_mul(Bigint const &a,Bigint const &b,Bigint &c);
}
#include <cmath>
#include <complex>
#include <vector>
#include <algorithm>
#include <iterator>
namespace Dodecahedron
{
class __fft
{
    typedef double real;
    typedef std::complex<real> cp;
    typedef std::vector<cp> arr;
    arr a,b,w,tt;
    int n;
    const real pi;
    int cpy(arr &d,Bigint const &s)
    {
        d.clear();
        for(std::vector<int>::const_iterator it(s.number.begin()); it!=s.number.end(); ++it)
        {
            d.push_back(cp(*it%10000,0));
            d.push_back(cp(*it/10000,0));
        }
        return d.size();
    }
    void dft(arr &a,int s,int t)
    {
        if((n>>t)==1) return;
        dft(a,s,t+1);
        dft(a,s+(1<<t),t+1);
        for(int i=0; i<(n>>(t+1)); ++i)
        {
            int p=(i<<(t+1))+s;
            cp wt=w[i<<t]*a[p+(1<<t)];
            tt[i]=a[p]+wt;
            tt[i+(n>>(t+1))]=a[p]-wt;
        }
        for(int i=0; i<(n>>t); ++i)
            a[(i<<t)+s]=tt[i];
    }
    long long round(real x)
    {
        // WARNING: only works with positive number
        return x+0.5;
    }
    void back(Bigint &cc)
    {
        std::vector<long long> c(n+1);
        for(int i=0; i<n; ++i)
        {
            c[i]+=round(a[i].real()/n);
            c[i+1]=c[i]/10000;
            c[i]%=10000;
        }
        if(!c.empty())
        {
            long long incs;
            while((incs=c.back())>=10000)
            {
                c.back()%=10000;
                c.push_back(incs/10000);
            }
        }
        while(!c.empty()&&!c.back())
            c.pop_back();
        cc.number.clear();
        for(std::vector<long long>::const_iterator it(c.begin()); it<c.end(); it+=2)
        {
            int tmp1=*it;
            int tmp2=it+1==c.end()?0:*(it+1);
            cc.number.push_back(tmp1+tmp2*10000);
        }
    }
public:
    __fft():pi(std::acos((real)-1.0)) {}
    void set(Bigint const &a,Bigint const &b)
    {
        n=1;
        int lla=cpy(this->a,a);
        int llb=cpy(this->b,b);
        while((n>>1)<lla)n+=n;
        while((n>>1)<llb)n+=n;
        for(int i=0; i<n; ++i)
            w.push_back(cp(std::cos(pi*2*i/n),std::sin(pi*2*i/n)));
        this->a.resize(n);
        this->b.resize(n);
        tt.resize(n);
    }
    void mul(Bigint &c)
    {
        dft(a,0,0);
        dft(b,0,0);
        for(int i=0; i<n; ++i)
            a[i]=a[i]*b[i];
        for(int i=0; i<n; ++i)
            w[i]=cp(w[i].real(),-w[i].imag());
        dft(a,0,0);
        back(c);
    }
};
void __fft_mul(Bigint const &a,Bigint const &b,Bigint &c)
{
    __fft f;
    f.set(a,b);
    f.mul(c);
}
}

#endif


namespace Dodecahedron
{

//Constructor
Bigint::Bigint()
        : positive(true),
          force_fft(false)
          {}
Bigint::Bigint(const Bigint &b)
        : number(b.number),
          positive(b.positive),
          force_fft(false)
          {}
Bigint::Bigint(long long value)
:force_fft(false){
    if (value < 0) {
        positive = false;
        value *= -1;
    } else {
        positive = true;
    }

    while (value) {
        number.push_back((int) (value % Bigint::default_base));
        value /= Bigint::default_base;
    }
}

Bigint::Bigint(std::string stringInteger)
:force_fft(false){
    int size = stringInteger.length();

    positive = (stringInteger[0] != '-');

    while (true) {
        if (size <= 0) break;
        if (!positive && size <= 1) break;

        int length = 0;
        int num = 0;
        int prefix = 1;
        for (int i(size - 1); i >= 0 && i >= size - Bigint::default_digits_per_element; --i) {
            if (stringInteger[i] < '0' || stringInteger[i] > '9') break;
            num += (stringInteger[i] - '0') * prefix;
            prefix *= 10;
            ++length;
        }
        number.push_back(num);
        size -= length;
    }
    delete_precode_zero();
}

//Adding
Bigint Bigint::operator+(Bigint const &b) const
{
    Bigint c = *this;
    c += b;

    return c;
}

Bigint &Bigint::operator+=(Bigint const &b)
{
    if (positive && !b.positive) {
        b.flip_positive();
        *this -= b;
        b.flip_positive();
        return *this;
    }
    if (!positive && b.positive) {
        flip_positive();
        *this -= b;
        flip_positive();
        return *this;
    }
    if (!positive && !b.positive) {
        flip_positive();
        b.flip_positive();
        *this += b;
        flip_positive();
        b.flip_positive();
        return *this;
    }
    std::vector<int>::iterator
        it1 = number.begin();
    std::vector<int>::const_iterator
        it2 = b.number.begin();
    int sum = 0;
    while (it1 != number.end() || it2 != b.number.end()) {
        if (it1 != number.end()) {
            sum += *it1;
        } else {
            number.push_back(0);
            it1 = number.end()-1;
        }
        if (it2 != b.number.end()) {
            sum += *it2;
            ++it2;
        }
        *it1 = sum % Bigint::default_base;
        ++it1;
        sum /= Bigint::default_base;
    }
    if (sum) number.push_back(1);

    return *this;
}

//Subtraction
Bigint Bigint::operator-(Bigint const &b) const
{
    Bigint c = *this;
    c -= b;

    return c;
}

Bigint &Bigint::operator-=(Bigint const &b)
{
    if (!positive || !b.positive){
        b.flip_positive();
        *this += b;
        b.flip_positive();
        return *this;
    }
    std::vector<int>::iterator
        it1 = number.begin();
    std::vector<int>::const_iterator
        it2 = b.number.begin();
    int dif = 0;
    while (it1 != number.end() || it2 != b.number.end()) {
        if (it1 != number.end()) {
            dif += *it1;
            ++it1;
        } else {
            number.push_back(0);
            it1 = number.end();
        }
        if (it2 != b.number.end()) {
            dif -= *it2;
            ++it2;
        }
        if (dif < 0) {
            *(it1 - 1) = (dif + Bigint::default_base) % Bigint::default_base;
            dif = -1;
        } else {
            *(it1 - 1) = dif % Bigint::default_base;
            dif /= Bigint::default_base;
        }
    }
    if (dif < 0) {
        std::string newstr("1");
        int c_seg = number.size();
        while(c_seg--)
            for(int i=1; i<Bigint::default_base; i*=10)
                newstr += "0";
        *this = Bigint(newstr) - *this;
        positive = false;
    }
    delete_precode_zero();

    return *this;
}

//Multiplication
static bool is_fft_needed(unsigned long long a, unsigned long long b)
{
    return a * b >
#   ifdef BIGINT_FFT_TRIGGER
        BIGINT_FFT_TRIGGER
#   else
        1024 * 1024
#   endif
    ;
}
Bigint Bigint::operator*(Bigint const &b) const
{
    if (force_fft || b.force_fft || is_fft_needed(this->number.size(), b.number.size()))
    {
        Bigint c;
        bool result_positive = !(positive ^ b.positive);
        __fft_mul(*this, b, c);
        c.positive = result_positive;
        return c;
    }

    const long long max_longlong =
        static_cast<long long>(
            static_cast<unsigned long long>(
                static_cast<long long>(-1)
            ) >> 1
        );
    const long long update_limit =
        max_longlong - static_cast<long long>(Bigint::default_base - 1) * (Bigint::default_base - 1);
    bool update_flag = false;

    Bigint const &a = *this;
    Bigint c;
    std::vector<long long> number(a.number.size()+b.number.size());
    for(std::vector<int>::const_iterator
        it1(a.number.begin()); it1!=a.number.end(); ++it1){
        update_flag = false;
        for(std::vector<int>::const_iterator
            it2(b.number.begin()); it2!=b.number.end(); ++it2)
            update_flag = ((
                number[
                    (it1 - a.number.begin()) +
                    (it2 - b.number.begin()) ]
                += static_cast<long long>(*it1) * *it2
            ) > update_limit || update_flag);
        if(update_flag)
            for(std::vector<long long>::iterator it(number.begin() + 1);
                it < number.end(); ++it){
                *it += *(it - 1) / Bigint::default_base;
                *(it - 1) %= Bigint::default_base;
            }
    }
    if(!update_flag)
        for(std::vector<long long>::iterator it(number.begin() + 1);
            it < number.end(); ++it){
            *it += *(it - 1) / Bigint::default_base;
            *(it - 1) %= Bigint::default_base;
        }
    c.positive = !(a.positive ^ b.positive);
    std::copy(number.begin(), number.end(), std::back_inserter(c.number));
    c.delete_precode_zero();
    return c;
}

Bigint &Bigint::operator*=(Bigint const &b)
{
    return *this = *this * b;
}

static std::string to_string(const int value)
{
    char str[16];
    std::sprintf(str, "%d", value);
    return str;
}

Bigint sub_number(Bigint &p, Bigint &q){

      std::string tmpx0, tmpx1, tmpx3;
      long window_size = q.digits();
      int last_i_iterator;
      std::vector<int>::iterator i=p.number.end()-1;

      if(window_size>p.digits())
          window_size=p.digits();


      while(i>=p.number.begin() && window_size>0){

          tmpx0 = to_string(*i);
          int ssss = tmpx0.size();
          if(i!=p.number.end()-1 && ssss<Bigint::default_digits_per_element){
              tmpx0 = std::string(Bigint::default_digits_per_element-ssss,'0') + tmpx0;
          }

          if(window_size - ssss < 0){
              tmpx3=tmpx0;
              tmpx0="";
              for(int i=0;i<window_size;i++){
                  tmpx0=tmpx0+tmpx3[i];
                  last_i_iterator=i;
              }
              window_size = window_size - tmpx0.size();
              tmpx1 = tmpx1 + tmpx0;
          }
          else{
              window_size = window_size - tmpx0.size();
              tmpx1 = tmpx1 + tmpx0;
              i--;
          }
      }

      Bigint c(tmpx1);

      if(c<q && i>=p.number.begin()){
          if(tmpx3.size()!=0){
              window_size++;
              tmpx0 = tmpx3[last_i_iterator+1];
              tmpx1 = tmpx1 + tmpx0;
              c=tmpx1;
          }
          else{
              window_size++;
              tmpx0 = to_string(*i);
              if(i!=p.number.end()-1 && tmpx0.size()<Bigint::default_digits_per_element){
                  tmpx0 = std::string(Bigint::default_digits_per_element-tmpx0.size(),'0') + tmpx0;
              }
              tmpx0 = tmpx0[0];
              tmpx1 = tmpx1 + tmpx0;
              c=tmpx1;
          }

      }

      return c;
}
//Division
void divide(Bigint p, Bigint q, std::vector<Bigint> &answer){

    /*Algorithm used is "Double division algorithm"*/

    answer.clear();
    int look_up_table_size=4;
    std::vector<Bigint> look_up(look_up_table_size);
    bool done_flag=false ;
    Bigint tmp_quotient, sum_quotient, tmpx1, tmpx2;

    look_up[0]=q;
    look_up[1]=q*2;
    look_up[2]=q*4;
    look_up[3]=q*8;

    while(true){

       Bigint sub_p=sub_number(p, q);  // cut a portion from the dividened equal in size with the divisor

        for(int i=0;i<look_up_table_size;i++){ // looking in the look_up table

            if(sub_p<look_up[i] && i!=0){
                tmpx1=look_up[i-1];
                tmp_quotient = std::pow(2,i-1);
                break;
            }
            else if(sub_p<look_up[i] && i==0){

                if(q.digits()>=p.digits()){
                    done_flag=true;
                    break;
                }
            }
            else if(sub_p==look_up[i] || (sub_p>look_up[i] && i==look_up_table_size-1)){
                 tmpx1=look_up[i];
                 tmp_quotient= std::pow(2,i);
                break;
            }
        }

        if(done_flag){
            answer.push_back(sum_quotient);
            answer.push_back(sub_p);
            break;
        }

        std::string temppp(p.digits()-(sub_p.digits()),'0');
        temppp="1"+temppp;
        tmpx2=temppp;

        if(sum_quotient.digits()==0)
            sum_quotient=tmp_quotient*tmpx2;
        else
            sum_quotient=sum_quotient+(tmp_quotient*tmpx2);

        tmpx1=tmpx1*tmpx2;
        p=p-tmpx1;

    }

}

static void check_divisor(Bigint const &b)
{
    if (b == 0)
        throw Bigint::arithmetic_error("Divide by zero");
}

Bigint Bigint::operator/(Bigint const &b) const
{
    check_divisor(b);
    if (*this == 0) return 0;
    bool result_positive = !(positive ^ b.positive);
    bool origin_positive_this = positive;
    bool origin_positive_b    = b.positive;
    positive = true;
    b.positive = true;
    std::vector<Bigint> answer;
    divide(*this, b, answer);
    Bigint &ans = answer[0];
    positive = origin_positive_this;
    b.positive = origin_positive_b;
    ans.positive = result_positive;
    return ans;
}

Bigint &Bigint::operator/=(Bigint const &b)
{
    return *this = *this / b;
}

Bigint Bigint::operator%(Bigint const &b) const
{
    check_divisor(b);
    if (*this == 0) return 0;
    bool result_positive = positive;
    bool origin_positive_this = positive;
    bool origin_positive_b    = b.positive;
    positive = true;
    b.positive = true;
    std::vector<Bigint> answer;
    divide(*this, b, answer);
    Bigint &ans = answer[1];
    positive = origin_positive_this;
    b.positive = origin_positive_b;
    ans.positive = ans==0 ? true : result_positive;
    return ans;
}

Bigint &Bigint::operator%=(Bigint const &b)
{
    return *this = *this % b;
}

//Power

Bigint Bigint::pow(int const &power, std::map<int, Bigint> &lookup)
{
    if (power == 1) return *this;
    if (lookup.count(power)) return lookup[power];

    int closestPower = 1;
    while (closestPower < power) closestPower <<= 1;
    closestPower >>= 1;

    if (power == closestPower) lookup[power] = pow(power / 2, lookup) * pow(power / 2, lookup);
    else lookup[power] = pow(closestPower, lookup) * pow(power - closestPower, lookup);

    return lookup[power];
}

Bigint &Bigint::pow(int const &power)
{
    if (!power) return *this = Bigint(1);
    std::map<int, Bigint> lookup;
    if (power % 2 == 0 && !positive) {
        positive = true;
    }
    *this = pow(power, lookup);

    return *this;
}

//Compare
int Bigint::compare(const Bigint &a) const //0 this == a || -1 this < a || 1 this > a
{
    if (positive && !a.positive) return 1;
    if (!positive && a.positive) return -1;

    int check = 1;
    if (!positive && !a.positive) check = -1;

    if (number.size() < a.number.size()) return -1 * check;
    if (number.size() > a.number.size()) return check;
    for (size_t i(number.size()); i > 0; --i) {
        if (number[i-1] < a.number[i-1]) return -1 * check;
        if (number[i-1] > a.number[i-1]) return check;
    }

    return 0; // ==
}

bool Bigint::operator<(Bigint const &b) const
{
    return compare(b) == -1;
}

bool Bigint::operator<=(const Bigint &b) const
{
    int compared = compare(b);

    return compared == 0 || compared == -1;
}

bool Bigint::operator>(const Bigint &b) const
{
    return compare(b) == 1;
}

bool Bigint::operator>=(const Bigint &b) const
{
    int compared = compare(b);

    return compared == 0 || compared == 1;
}

bool Bigint::operator==(Bigint const &b) const
{
    return compare(b) == 0;
}

bool Bigint::operator!=(Bigint const &b) const
{
    return ! (*this == b);
}

//Allocation
Bigint Bigint::operator=(const long long &a)
{
    number.clear();
    long long t = a;
    do {
        number.push_back((int) (t % Bigint::default_base));
        t /= Bigint::default_base;
    } while (t != 0);

    return *this;
}

//Trivia
int Bigint::digits() const
{
    int segments = number.size();

    if (segments == 0) return 0;

    int digits = Bigint::default_digits_per_element * (segments - 1);
    digits += segment_length(number.back());

    return digits;
}

int Bigint::trailing_zeros() const
{
    if (number.empty() || (number.size() == 1 && number[0] == 0)) return 1;

    int zeros = 0;
    std::vector<int>::const_iterator it = number.begin();
    if (number.size() > 1) {
        for (; it != number.end() - 1 && *it == 0; ++it) {
            zeros += Bigint::default_digits_per_element;
        }
    }
    int a = *it;
    while (a % 10 == 0 && a) {
        ++zeros;
        a /= 10;
    }

    return zeros;
}

//Helpers
void Bigint::clear()
{
    number.clear();
    positive = true;
}

Bigint &Bigint::abs()
{
    positive = true;

    return *this;
}

void Bigint::flip_positive() const
{
    // WARN: private use, must call as pair!!!
    positive = !positive;
}

void Bigint::delete_precode_zero()
{
    while (!number.empty() && !number.back())
        number.pop_back();
}

//Input&Output
std::ostream &operator<<(std::ostream &out, Bigint const &a)
{
    if (!a.number.size()) return out << 0;
    int i = a.number.size() - 1;
    for (; i>=0 && a.number[i] == 0; --i);

    if (i == -1) return out << 0;
    if (!a.positive) out << '-';

    std::vector<int>::const_reverse_iterator it = a.number.rbegin() + (a.number.size() - i - 1);

    out << *it++;
    for (; it != a.number.rend(); ++it) {
        for (int i(0), len = a.segment_length(*it); i < Bigint::default_digits_per_element - len; ++i) out << '0';
        if (*it) out << *it;
    }

    return out;
}


std::istream &operator>>(std::istream &in, Bigint &a)
{
    std::string str;
    in >> str;

    a = str;

    return in;
}

int Bigint::segment_length(int segment) const
{
    int length = 0;
    while (segment) {
        segment /= 10;
        ++length;
    }

    return length;
}

Bigint abs(Bigint value)
{
    return value.abs();
}

std::string to_string(Bigint const &value)
{
    std::ostringstream stream;
    stream << value;

    return stream.str();
}

Bigint factorial(int n)
{
    Bigint result = 1;
    if (n % 2) {
        result = n;
        --n;
    }
    int last = 0;
    for (; n >= 2; n -= 2) {
        result *= n + last;
        last += n;
    }

    return result;
}

}

#include<iostream>
using namespace std;
using namespace Dodecahedron;
int main(){
    ios::sync_with_stdio(false);
    Bigint a,b;
    int n;
    cin>>n;
    while(n--){
        cin>>a>>b;
        cout<<a*b<<'\n';
    }
    return 0;
}

7

twd2 LV 9 MOD @ 2017-01-17 19:39:27

经过和同学讨论以及根据题目要求查阅相关资料，我查到了如下算法：

算法一

直接模拟手算乘法。

需要注意的是，由于除法和取模运算较慢，所以这里把进位操作延迟到所有乘法操作结束后一起执行。

两个n位数字，每位数字两两相乘，所以时间复杂度为O(n^2)；由于需要一个空间存储答案，所以空间复杂度是O(n)。

算法二

通过分解大整数为X = A * 1eY + B的形式（Y一般取为X位数的一半），再分别进行乘法，如此递归下去。

n为十进制位数，那么时间复杂度T(n) = 4T(n/2) + O(n), T(n) = O(n^2)，与强力算法一致。

但由于(Ax+B)(Cx+D) = ACx^2 + [(A+B)(C+D) - AC - BD]x + BD，其中x = 1e(Y = mid)

可以以此减少一次乘法，这样时间复杂度就是T(n) = 3T(n/2) + O(n)，T(n) = O(n^1.585)；同样，由于需要一个空间存储答案，所以空间复杂度是O(n)。

但是，这个算法常数可能较大，根据文献，在n > 500的时候，后者才会更快。

然而经过测试，我实现的算法二常数巨大，算法一已经足够快。

xiazhongyv @ 2017-03-23 10:33:00

“两个n位数字，每位数字两两相乘，所以时间复杂度为O(n)”
为什么不是O（n2）。。。。。
用户不存在 @ 2017-04-13 20:10:34

@xiazhongyv: 他应该是打错了吧
mrsrz @ 2017-07-27 10:21:50

然而我边乘边除边取模，还是卡过去了。
Bill_Yang @ 2017-08-02 22:36:15

@xiazhongyv: 他可能用的是FFT，然而我并不懂FFT压位
twd2 @ 2020-05-12 01:13:50

@xiazhongyv: 修了 >_<

5

twd2 LV 9 MOD @ 2017-01-17 19:38:38

压位的高精度。

注意尽量减少乘法和除法执行次数。例如，可以少压几位，然后将“边乘边进位”优化为“所有数乘完”再统一进位。

1

1942938446 LV 7 @ 2020-08-06 21:22:26

啊呀FFT不想写怎么办？

啊呀 Python 被卡了 TLE 怎么办？

自豪地使用 Ruby！

Ruby！自带高精！跑的比 C++ 快！想卡都卡不掉！
n = gets.to_i for i in 1..n a,b = gets.split.map(&:to_i) print a*b puts("\n") end
好了，没了。

0

1697749107 LV 8 @ 2018-12-19 11:33:37

#include<iostream>
#include<cstring>
using namespace std;
const int maxn=10005;
int a[maxn],b[maxn],ans[maxn],n;
char s1[maxn],s2[maxn];
int main()
{
cin>>n;
while(n--){
cin>>s1>>s2;
a[0]=strlen(s1);
b[0]=strlen(s2);
for(int i=a[0];i>=1;i--)
a[i]=s1[a[0]-i]-'0';
for(int i=b[0];i>=1;i--)
b[i]=s2[b[0]-i]-'0';
ans[0]=a[0];
for(int i=1;i<=a[0];i++)
for(int j=1;j<=b[0];j++)
{
ans[i+j-1]=b[j]*a[i];
if(ans[i+j-1]>9) ans[i+j]+=ans[i+j-1]/10,ans[i+j-1]%=10;
}
for(int i=a[0]+b[0];!ans[i];i--);
ans
for(int i=ans[0];i>=1;i--)
cout<<ans[i];
cout<<"\n";
}
return 0;
}

0

XSPEC LV 8 @ 2018-10-19 19:10:33

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 5010
using namespace std;
const int P=8;
const long long BASE=1e8;
struct bign
{
long long s[MAXN];
bign(){memset(s,0,sizeof s);}
bign(char ss,int len)
{
int t=0;memset(s,0,sizeof s);
for (int i=0,w;i<len;w=10,i++)
{
if (i%P==0){w=1;t++;}
s[t]+=w*(ss[i]-'0');
}
s[0]=t;
}
void print()
{
printf("%lld",s[s[0]]);
for (int i=s[0]-1;i;i--) printf("%0*lld",P,s[i]);
puts("");
}
};
attribute((optimize("-O2")))
void operator * (const bign &a,const bign &b)
{
bign c;
c.s[0]=a.s[0]+b.s[0]-1;
for (int i=1;i<=a.s[0];i++)
for (int j=1;j<=b.s[0];j++)
c.s[i+j-1]+=a.s[i]*b.s[j];
for (int i=1;i<=c.s[0];i++)
if (c.s[i]>=BASE)
{
c.s[i+1]+=c.s[i]/BASE;
c.s[i]%=BASE;
}
if (c.s[c.s[0]+1]) c.s[0]++;
c.print();
return ;
}
int T,slen,tlen;
char s[MAXN],t[MAXN];
bign a,b,c;
attribute((optimize("-O2")))
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%s",s);scanf("%s",t);
slen=strlen(s);tlen=strlen(t);
reverse(s,s+slen);reverse(t,t+tlen);
a=bign(s,slen);b=bign(t,tlen);
a*b;
}
return 0;
}

0

qq913653500 LV 10 @ 2017-08-18 11:38:29

#include <vector>
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
struct BigInt
{
static const int Base = 100000000;
static const int Width = 8;
vector <int> s;
BigInt (long long num = 0)
{
*this = num;
}
BigInt operator = (long long num)
{
s.clear();
do
{
s.push_back(num % Base);
num /= Base;
}while (num > 0);
return *this;
}
BigInt operator + (const BigInt &b) const
{
BigInt res;
res.s.clear();
for (int i = 0, count = 0;;i++)
{
if (count == 0 && i >= s.size() && i >= b.s.size()) break;
int x = count;
if (i < s.size()) x += s[i];
if (i < b.s.size()) x += b.s[i];
res.s.push_back(x % Base);
count = x / Base;
}
return res;
}

BigInt operator - (const BigInt &b) const
{
BigInt res;
res.s.clear();
for (int i = 0, carry = 0;;i++)
{
if (carry == 0 && i >= s.size() && i >= b.s.size()) break;
int x = carry;
carry = 0;
if (i < s.size()) x += s[i]; else break;
if (i < b.s.size()) x -= b.s[i];
if (x < 0)
{
carry = -1;
x += Base;
}
res.s.push_back(x %Base);
}
return res;
}
friend ostream& operator << (ostream &out, const BigInt& x)
{
out << x.s.back();
for(int i = x.s.size()-2; i >= 0; i--)
{
char buf[20];
sprintf(buf, "%08d", x.s[i]);
for(int j = 0; j < strlen(buf); j++) out << buf[j];
}
return out;
}
};

int main()
{
int n;
scanf("%d",&n);
BigInt f[4]={0,0,1,2},g[4]={0,1,1,4};
if (n < 4) cout << f[n] + f[n];
else
{
for (int i = 4; i <=n; i++)
{
f[i%4] = f[(i-1)%4] + g[(i-1)%4];
g[i%4] = f[(i-1)%4] + f[(i-1)%4] + g[(i-1)%4] +g[(i-2)%4] -g[(i-3)%4];
}
cout << f[n%4] + f[n%4];
}

}

0

hzk123 LV 9 @ 2017-08-14 18:23:57

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN 10000

#define pi acos(-1.0) // PI值
using namespace std;
const double PI=acos(-1);
const int u=5;
struct Complex
{
    double x,y;
    Complex(double _x=0.0,double _y=0.0)
    {
        x=_x;
        y=_y;
    }
    Complex operator -(const Complex &b)const
    {
        return Complex(x-b.x,y-b.y);
    }
    Complex operator +(const Complex &b)const
    {
        return Complex(x+b.x,y+b.y);
    }
    Complex operator *(const Complex &b)const
    {
        return Complex(x*b.x-y*b.y,x*b.y+y*b.x);
    }
};


Complex x1[MAXN],x2[MAXN];
void change(Complex y[],int len)
{
    int i,j,k;
    for (i = 1,j=len/2; i<len-1;i++)
    {
        if (i<j) swap(y[i],y[j]);
        k=len/2;
        while (j>=k)
        {
            j-=k;
            k/=2;
        }
        if (j<k) j+=k;
    }
}

void fft(Complex y[],int len,int on)
{
    change(y,len);
    for (int h=2;h<=len;h<<=1)
    {
        Complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h));
        for (int j=0;j<len;j+=h)
        {
            Complex w(1,0);
            for (int k=j; k<j+h/2; k++)
            {
                Complex u=y[k];
                Complex t=w*y[k+h/2];
                y[k] = u+t;
                y[k+ h/2] = u-t;
                w=w*wn;
            }
        }
    }

    if (on==-1)
        for (int i=0;i<len;i++)
        y[i].x/=len;
}

int rs[10];
char a[MAXN],b[MAXN],c[MAXN];
unsigned long long sum[MAXN];
int main(void)
{
    int l1,l2,l,T;
    register int i;
    double tmp;
    scanf("%d",&T);

    while(T--)
    {
        scanf("%s%s",a,b);
        l1=strlen(a);
        l2=strlen(b);
        for (int i=0;i<l1;i++) c[i] = a[l1-1-i];
         for (int i=0;i<l1;i++) a[i] = c[i];
         for (int i=0;i<l2;i++) c[i] = b[l2-1-i];
         for (int i=0;i<l2;i++) b[i] = c[i];
        memset(sum,0,sizeof sum);
        l=1;
        int t1=l1/u + (l1%u==0?0:1 );
        int t2=l2/u + (l2%u==0?0:1 );
        int tmp1=1,tmp2=1;
        while (tmp1 < t1) tmp1*=2;
        while (tmp2 < t2) tmp2*=2;
        while( l<tmp1 + tmp2 )   l<<=1;

        for(i=0;i< t1 ; i++)
        {
            tmp = 0;
            for (int j=min(l1-1,i*u+u-1);j>=i*u  ;j--)
                tmp = tmp * 10 + a[j] - '0';
            x1[i].x= tmp;
            x1[i].y=0.0;
        }
        for (i=t1;i<l;i++) x1[i].x=x1[i].y=0.0;

        for(i=0;i< t2  ;i++)
        {
            tmp = 0;
            for (int j=min(l2-1,i*u+u-1);j>=i*u ;j--)
                tmp = tmp * 10 + b[j] - '0' ;
            x2[i].x= tmp;
            x2[i].y=0.0;
        }
        for(i=t2;i<l;i++)    x2[i].x=x2[i].y=0.0;
        fft(x1,l,1);
        fft(x2,l,1);
        for(i=0;i<l;i++) x1[i]=x1[i]*x2[i];
        fft(x1,l,-1);
        for(i=0;i<l;i++) sum[i]=x1[i].x+0.5;

        unsigned long long md=1;
        for (int i=0;i<u;i++) md*=10;

        for(i=0;i<l;i++)
        {
            sum[i+1]+=sum[i]/md;
            sum[i]%=md;
        }
        while(sum[l]<=0 && l>0)   l--;
        if (l==0 && sum[0]==0) printf("0");
        else
        {
            printf("%u",sum[l]);
            for(int i=l-1;i>=0;i--)
            {
               memset(rs,0,sizeof rs);
               for (int j=0;j<u;j++)
                    rs[j] = sum[i] % 10,sum[i]/=10;
               for (int j=u-1;j>=0;j--)
                   printf("%d",rs[j]);
            }
        }
        puts("");
    }
    return 0;
}

0

hzk123 LV 9 @ 2017-08-14 18:22:54

压5位FFT ，6位压了要炸

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN 10000

#define pi acos(-1.0) // PI值
using namespace std;
const double PI=acos(-1);
const int u=5;
struct Complex
{
    double x,y;
    Complex(double _x=0.0,double _y=0.0)
    {
        x=_x;
        y=_y;
    }
    Complex operator -(const Complex &b)const
    {
        return Complex(x-b.x,y-b.y);
    }
    Complex operator +(const Complex &b)const
    {
        return Complex(x+b.x,y+b.y);
    }
    Complex operator *(const Complex &b)const
    {
        return Complex(x*b.x-y*b.y,x*b.y+y*b.x);
    }
};


Complex x1[MAXN],x2[MAXN];
void change(Complex y[],int len)
{
    int i,j,k;
    for (i = 1,j=len/2; i<len-1;i++)
    {
        if (i<j) swap(y[i],y[j]);
        k=len/2;
        while (j>=k)
        {
            j-=k;
            k/=2;
        }
        if (j<k) j+=k;
    }
}

void fft(Complex y[],int len,int on)
{
    change(y,len);
    for (int h=2;h<=len;h<<=1)
    {
        Complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h));
        for (int j=0;j<len;j+=h)
        {
            Complex w(1,0);
            for (int k=j; k<j+h/2; k++)
            {
                Complex u=y[k];
                Complex t=w*y[k+h/2];
                y[k] = u+t;
                y[k+ h/2] = u-t;
                w=w*wn;
            }
        }
    }

    if (on==-1)
        for (int i=0;i<len;i++)
        y[i].x/=len;
}

int rs[10];
char a[MAXN],b[MAXN],c[MAXN];
unsigned long long sum[MAXN];
int main(void)
{
    int l1,l2,l,T;
    register int i;
    double tmp;
    scanf("%d",&T);

    while(T--)
    {
        scanf("%s%s",a,b);
        l1=strlen(a);
        l2=strlen(b);
        for (int i=0;i<l1;i++) c[i] = a[l1-1-i];
         for (int i=0;i<l1;i++) a[i] = c[i];
         for (int i=0;i<l2;i++) c[i] = b[l2-1-i];
         for (int i=0;i<l2;i++) b[i] = c[i];
        memset(sum,0,sizeof sum);
        l=1;
        int t1=l1/u + (l1%u==0?0:1 );
        int t2=l2/u + (l2%u==0?0:1 );
        int tmp1=1,tmp2=1;
        while (tmp1 < t1) tmp1*=2;
        while (tmp2 < t2) tmp2*=2;
        while( l<tmp1 + tmp2 )   l<<=1;

        for(i=0;i< t1 ; i++)
        {
            tmp = 0;
            for (int j=min(l1-1,i*u+u-1);j>=i*u  ;j--)
                tmp = tmp * 10 + a[j] - '0';
            x1[i].x= tmp;
            x1[i].y=0.0;
        }
        for (i=t1;i<l;i++) x1[i].x=x1[i].y=0.0;

        for(i=0;i< t2  ;i++)
        {
            tmp = 0;
            for (int j=min(l2-1,i*u+u-1);j>=i*u ;j--)
                tmp = tmp * 10 + b[j] - '0' ;
            x2[i].x= tmp;
            x2[i].y=0.0;
        }
        for(i=t2;i<l;i++)    x2[i].x=x2[i].y=0.0;
        fft(x1,l,1);
        fft(x2,l,1);
        for(i=0;i<l;i++) x1[i]=x1[i]*x2[i];
        fft(x1,l,-1);
        for(i=0;i<l;i++) sum[i]=x1[i].x+0.5;

        unsigned long long md=1;
        for (int i=0;i<u;i++) md*=10;

        for(i=0;i<l;i++)
        {
            sum[i+1]+=sum[i]/md;
            sum[i]%=md;
        }
        while(sum[l]<=0 && l>0)   l--;
        if (l==0 && sum[0]==0) printf("0");
        else
        {
            printf("%u",sum[l]);
            for(int i=l-1;i>=0;i--)
            {
               memset(rs,0,sizeof rs);
               for (int j=0;j<u;j++)
                    rs[j] = sum[i] % 10,sum[i]/=10;
               for (int j=u-1;j>=0;j--)
                   printf("%d",rs[j]);
            }
        }
        puts("");
    }
    return 0;
}

0

Bill_Yang LV 10 @ 2017-08-02 21:45:48

噗，亿进制强行O2卡过
没办法，谁叫FFT10分。。。

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
typedef long long LL;
const int BASE=100000000; //高进制
const int WIDTH=8; //高进制位数
struct BigInteger {
vector<LL>s;
BigInteger() { //构造函数：初始赋0
*this=0;
}
BigInteger(const LL& num) { // 构造函数
*this=num;
}
//赋值
BigInteger operator = (LL num) {
s.clear();
do {
s.push_back(num%BASE);
num/=BASE;
} while(num>0);
return *this;
}
BigInteger operator = (const string& str) {
s.clear();
LL x;
int len=(str.length()-1)/WIDTH+1;
for(int i=0; i<len; i++) {
int end=str.length()-i*WIDTH;
int start=max(0,end-WIDTH);
sscanf(str.substr(start,end-start).c_str(),"%lld",&x);
s.push_back(x);
}
return *this;
}
BigInteger operator * (const BigInteger& b) {
BigInteger c;
c.s.resize(s.size()+b.s.size());
for(int i=0; i<s.size(); i++)
for(int j=0; j<b.s.size(); j++)c.s[i+j]+=s[i]*b.s[j];
for(int i=0; i<c.s.size()-1; i++) {
c.s[i+1]+=c.s[i]/BASE;
c.s[i]%=BASE;
}
while(c.s.back()==0&&c.s.size()>1)c.s.pop_back();
return c;
}
void operator *= (const BigInteger& b) {
*this=*this*b;
}
friend istream& operator >> (istream& input,BigInteger& x) {
string s;
if(!(input>>s))return input;
x=s;
return input;
}
friend ostream& operator << (ostream& output,const BigInteger& x) {
output<<x.s.back();
for(int i=x.s.size()-2; i>=0; i--) {
char buf[20];
sprintf(buf,"%08lld",x.s[i]);
for(int j=0; j<strlen(buf); j++)output<<buf[j];
}
return output;
}
};
BigInteger a,b;
int t;
__attribute__((__optimize__("-O2"))) int main() {
cin>>t;
while(t--) {
cin>>a>>b;
cout<<a*b<<endl;
}
return 0;
}

0

yql LV 8 @ 2016-10-25 14:53:48

这题好像必须1.5次FFT，然后常数还必须很小

0

HeRaNO (heran1999) LV 10 @ 2016-10-07 00:16:10

FFT就是这么神奇的东西，自己写会T，别人写A的到自己手里也会T
T_T
这数据有多毒？我HDU1402都过了求解QAQ

0

HeRaNO (heran1999) LV 10 @ 2016-10-06 22:37:30

数据好毒啊......
感觉得用FFT了
可是FFT用多了你会T的
QAQ

-1

苛性氢 LV 9 @ 2020-03-08 22:56:31

事实证明不需要-O2，也不需要FFT...
朴素亿进制，最长一组435ms

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

struct bint
{
    static const int BASE = 100000000;
    static const int WIDTH = 8;
    vector<int> s;
    inline int compare(const bint&a,const bint&b);
    inline unsigned int digit(long long x)
    {
        int r=0;
        while(x)
        {
            x=x/10,r++;
        }
        return (r?r:1);
    }
    inline unsigned int digit()
    {
        cleanzero();
        long long x=s.back();
        return digit(x)+(s.size()-1)*WIDTH;
    }
    inline bool operator ! () const
    {
        if(!s.size()) return true;
        for(unsigned int i=0; i<s.size(); i++) if(s[i]) return false;
        return true;
    }
    inline bint cleanzero()
    {
        if(!s.size())s.push_back(0);
        while(s.back()==0&&s.size()>1)s.pop_back();
        return *this;
    }
    inline bint(long long num=0)
    {
        *this = num;
    }
    inline bint operator = (long long num)
    {
        s.clear();
        do
        {
            s.push_back(num%BASE);
            num/=BASE;
        }
        while(num > 0);
        cleanzero();
        return *this;
    }
    inline bint operator = (bint b)
    {
        b.cleanzero();
        s.clear();
        s=b.s;
        return *this;
    }
    inline bint operator = (const string& str)
    {
        s.clear();
        int digits=str.length();
        while(digits>0)
            if(digits>WIDTH)
            {
                digits-=WIDTH;
                s.push_back(stoi(str.substr(digits,WIDTH).c_str()));
            }
            else
            {
                s.push_back(stoi(str.substr(0,digits).c_str()));
                break;
            }
        this->cleanzero();
        return *this;
    }
    inline bint operator + (const bint& b) const
    {
        bint r;
        r.s.clear();
        for(unsigned int i=0,x=0; (x>0)||(i<s.size())||(i<b.s.size()); i++,x=x/BASE)
        {
            if (i<s.size()) x+=s[i];
            if (i<b.s.size()) x+=b.s[i];
            r.s.push_back(x%BASE);
        }
        r.cleanzero();
        return r;
    }
    inline bint operator * (const int c) const
    {
        bint r;
        if((!c)||(!*this))
        {
            r=0;
            return r;
        }
        r.s.clear();
        long long x=0;
        for(unsigned int i=0; (x>0)||(i<s.size()+3); i++,x/=BASE)
        {
            if (i<s.size()) x+=(long long)(s[i])*c;
            r.s.push_back((int)(x%BASE));
        }
        r.cleanzero();
        return r;
    }
    inline bint operator * (const bint b) const
    {
        bint r;
        if((!b)||(!*this))
        {
            r=0;
            return r;
        }
        r.s.clear();
        long long x=0;
        for(unsigned int i=0; (x>0)||(i<s.size()+b.s.size()+1); i++,x/=BASE)
        {
            if (i<s.size()+b.s.size())
                for (unsigned int j=0; j<=i&&j<s.size(); j++)
                    if(i-j<b.s.size())
                    {
                        /*cout<<"j: "<<j<<", s: "<<s[j]<<" * b.s: "<<b.s[i-j]<<" = "<<(long long)(s[j])*(long long)(b.s[i-j])<<endl;*/x+=(long long)(s[j])*(long long)(b.s[i-j]);
                    }
            r.s.push_back((int)(x%BASE));//cout<<"i: "<<", x: "<<x<<endl<<endl;
        }
        r.cleanzero();
        return r;
    }
    inline bint operator << (const int c) const
    {
        bint r;
        r.s=s;
        r<<=c;
        return r;
    }
    inline bint operator >> (const int c) const
    {
        bint r;
        r.s=s;
        r>>=c;
        return r;
    }
    inline bint operator +=(const bint& b)
    {
        *this = *this + b;
        return *this;
    }
    inline bint operator *=(const int c)
    {
        *this = *this *c;
        return *this;
    }
    inline bint operator >>=(const int c)
    {
        for(int i=0; i<c&&s.size(); i++) s.erase(s.begin());
        cleanzero();
        return *this;
    }
    inline bint operator <<=(const int c)
    {
        for(int i=0; i<c; i++) s.insert(s.begin(),0);
        cleanzero();
        return *this;
    }
    inline int compare (const bint& b) const
    {
        if(s.size()!=b.s.size()) return (s.size()<b.s.size())?-1:1;
        for(int i = s.size()-1; i>=0; i--)
            if(s[i]!=b.s[i]) return (s[i]<b.s[i])?-1:1;
        return 0;
    }
    inline bool operator <  (const bint& b) const
    {
        return (compare(b)< 0);
    }
    inline bool operator >  (const bint &b) const
    {
        return (compare(b)> 0);
    }
    inline bool operator <= (const bint &b) const
    {
        return (compare(b)<=0);
    }
    inline bool operator >= (const bint &b) const
    {
        return (compare(b)>=0);
    }
    inline bool operator != (const bint &b) const
    {
        return (  compare(b) );
    }
    inline bool operator == (const bint &b) const
    {
        return ( !compare(b) );
    }

};

inline int compare(const bint&a,const bint&b)
{
    return a.compare(b);
}
inline unsigned int digit(bint      a)
{
    return a.digit();
}
inline unsigned int digit(long long x)
{
    int r=0;
    while(x)
    {
        x=x/10,r++;
    }
    return (r?r:1);
}

ostream& operator << (ostream &out, const bint& x)
{
    out << x.s.back();
    static constexpr char zerodigit[10]="00000000";
    for (int i=x.s.size()-2; i>=0; i--)
        out<<zerodigit+(int)digit(x.s[i])<<x.s[i];
    return out;
}

istream& operator >> (istream &in, bint& x)
{
    string s;
    if(in>>s)x=s;
    return in;
}

int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        bint a,b;
        cin>>a>>b;
        cout<<a*b<<endl;
    }
    return 0;
}

麒麟吃稀饭 @ 2021-07-20 20:17:10

fw

-1

HeRaNO (heran1999) LV 10 @ 2017-01-02 17:58:15

糟烂的代码，见谅

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 5010
using namespace std;

const int P=8;
const long long BASE=1e8;

struct bign
{
    long long s[MAXN];
    bign(){memset(s,0,sizeof s);}
    bign(char *ss,int len)
    {
        int t=0;memset(s,0,sizeof s);
        for (int i=0,w;i<len;w*=10,i++)
        {
            if (i%P==0){w=1;t++;}
            s[t]+=w*(ss[i]-'0');
        }
        s[0]=t;
    }
    void print()
    {
        printf("%lld",s[s[0]]);
        for (int i=s[0]-1;i;i--) printf("%0*lld",P,s[i]);
        puts("");
    }
};

__attribute__((__optimize__("-O2"))) void operator * (const bign &a,const bign &b)
{
    bign c;
    c.s[0]=a.s[0]+b.s[0]-1;
    for (int i=1;i<=a.s[0];i++)
        for (int j=1;j<=b.s[0];j++)
            c.s[i+j-1]+=a.s[i]*b.s[j];
    for (int i=1;i<=c.s[0];i++)
        if (c.s[i]>=BASE)
        {
            c.s[i+1]+=c.s[i]/BASE;
            c.s[i]%=BASE;
        }
    if (c.s[c.s[0]+1]) c.s[0]++;
    c.print();
    return ;
}

int T,slen,tlen;
char s[MAXN],t[MAXN];
bign a,b,c;

__attribute__((__optimize__("-O2"))) int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%s",s);scanf("%s",t);
        slen=strlen(s);tlen=strlen(t);
        reverse(s,s+slen);reverse(t,t+tlen);
        a=bign(s,slen);b=bign(t,tlen);
        a*b;
    }
    return 0;
}

-2

YLFX LV 6 @ 2017-05-09 16:57:06

#include <cstdio> #include <iostream> #include<cstring> using namespace std; int main() { char a[10],b[10]; int i,j; long long asum=1,bsum=1; cin>>a; cin>>b; for(i=0;i<strlen(a);i++){ asum*=a[i]-'A'+1; bsum*=b[i]-'A'+1; } if((asum%47)==(bsum%47)) cout<<"GO"; else cout<<"STAY"; return 0; }

题解

16 条题解

啊呀FFT不想写怎么办？

啊呀 Python 被卡了 TLE 怎么办？

自豪地使用 Ruby！

A x B Problem

信息

状态

开发

支持

题解

16 条题解

啊呀FFT不想写怎么办？

啊呀 Python 被卡了 TLE 怎么办？

自豪地使用 Ruby！

A x B Problem

信息

状态

开发

支持

还没有账户？

登录