题解

16 条题解

  • 15
    @ 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
    @ 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的时候,后者才会更快。

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

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

      “两个n位数字,每位数字两两相乘,所以时间复杂度为O(n)”
      为什么不是O(n2)。。。。。

    • @ 2017-04-13 20:10:34

      @xiazhongyv: 他应该是打错了吧

    • @ 2017-07-27 10:21:50

      然而我边乘边除边取模,还是卡过去了。

    • @ 2017-08-02 22:36:15

      @xiazhongyv: 他可能用的是FFT,然而我并不懂FFT压位

    • @ 2020-05-12 01:13:50

      @xiazhongyv: 修了 >_<

  • 5
    @ 2017-01-17 19:38:38

    压位的高精度。

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

  • 1
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 2016-10-25 14:53:48

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

  • 0
    @ 2016-10-07 00:16:10

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

  • 0
    @ 2016-10-06 22:37:30

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

  • -1
    @ 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;
    }
    
  • -1
    @ 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
    @ 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; }

  • 1

信息

ID
2000
难度
9
分类
高精度 点击显示
标签
(无)
递交数
1093
已通过
84
通过率
8%
上传者