# 16 条题解

• @ 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);

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();
}

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"*/

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){
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;
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;
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;
}
``````
• @ 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: 修了 >_<

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

压位的高精度。

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

• @ 2020-08-06 21:22:26

# 自豪地使用 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 ```
好了，没了。

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

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

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

}

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

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

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

• @ 2016-10-25 14:53:48

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

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

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

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

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

• @ 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

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

8

(无)

1154

101

9%

4