バグ入り

hakatashi.cpp

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

const int SIZE = 100001;
class mint;
mint multiply(mint &lhs, mint &rhs, int n);
class mint {
public:
  mint() : data(SIZE) {}
  char &operator[](int i) {
    return data[i];
  }
  mint operator+(mint &rhs) {
    mint res;
    int carry = 0;
    for (int i=0;i<SIZE;++i){
      int x = rhs[i]+data[i]+carry;
      carry = 0;
      if (x >= 10) {
	carry = 1;
	x -= 10;
      }
      res[i] = x;
    }
    return res;
  }
  mint operator-(mint &rhs) {
    mint res;
    int carry = 0;
    for (int i=0;i<SIZE;i++){
      int x = data[i] - rhs[i] - carry;
      carry = 0;
      if (x < 0) {
	carry = 1;
	x += 10;
      }
      res[i] = x;
    }
    return res;
  }
  mint operator*(mint &rhs) {
    return multiply(*this,rhs,SIZE);
  }
  vector<char> data;
  int size;
};

mint sub(mint &v, int s, int e) {
  mint x;
  for (int i=s;i<e;i++){
    x[i-s]=v[i];
  }
  return x;
}

mint multiply(mint &lhs, mint &rhs, int n) {
  if (n == 1) {
    mint res;
    int x = rhs[0] * lhs[0];
    if (x >= 10) {
      res[0] = x-10;
      res[1] = 1;
    } else {
      res[0] = x;
    }
    return res;
  }
  int m = n/2;
  mint x0 = sub(lhs,0,m);
  mint y0 = sub(lhs,m+1,n);
  mint x1 = sub(rhs,0,m);
  mint y1 = sub(rhs,m+1,n);
  
  mint z0 = multiply(x0,y0,m);
  mint z1 = multiply(x1,y1,n-m);
  mint t0 = x0 + x1;
  mint t1 = y0 + y1;
  mint z2 = multiply(t0, t1, m) - z0 - z1;

  int carry = 0;
  for (int i=m;i<SIZE;++i){
    int x = z0[i]+z2[i]+carry;
    carry = 0;
    if (x >= 10) {
      carry = 1;
      x -= 10;
    }
    z0[i] = x;
  }
  for (int i=m*2;i<SIZE;++i){
    int x = z0[i]+z1[i]+carry;
    carry = 0;
    if (x >= 10) {
      carry = 1;
      x -= 10;
    }
    z0[i] = x;
  }
  return z0;
}

int main() {
  char c;
  mint v;
  int k=0;
  while (~scanf("%c",&c)) {
    v[k] = c-'0';
    ++k;
  }
  puts("done");
  for (int i=0;i<SIZE/2;++i) {
    int t=v[SIZE-i];
    v[SIZE-i] = v[i];
    v[i] = t;
  }
  mint res = v*v;
  int keta=0;
  for (int i=0;i<SIZE;++i){
    if (res[i]) {
      keta=i;
    }
  }
  ++keta;
  for (int i=0;i<keta;++i) {
    printf("%c",res[i]);
  }
  puts("");
}