8050 | naoya_t | CARM | CPP | Accepted | 3.2305

#include <vector>
#include <set>
#include <string>
#include <stack>
#include <sstream>
#include <iostream>
#include <cstdlib>
using namespace std;

typedef long long LL;

LL random(LL n){return (LL)rand()%n;}
LL c1(LL m,LL a){LL r=a*a%m;return(1LL<a&&a<m-1&&r==1)?0:r;}
LL expmod(LL base,LL exp,LL m){if(!exp)return 1;else if(!(exp&1))return c1(m,expmod(base,exp/2,m));else return base*expmod(base,exp-1,m)%m;}
bool mr(LL n){return expmod((1LL+random(n-1)),n-1,n)==1;}
bool pq(LL n,int times=4){
  if(n==1)return false;
  if(n==2)return true;
  else if(!(n&1))return false;
  for(int i=times;i>0;i--)if(!mr(n))return false;
  return true;}

class Bn {
  int sign;
  int size;
  vector<LL> values;

  int remainder_;

 public:
  Bn(int val=0){set(val);}
  Bn(const Bn& num){set(num);}

  void set(int val);
  void set(const Bn& num);

 private:
  bool is_zero() const { return (size==1 && values[0]==0)? true : false; };
  void normalize();

  char enc(int n) const { return n<10 ? '0'+n : 'A'+(n-10); }
  int dec(int ch) const { return ch<='9' ? ch-'0' : 10+ch-'A'; }

 public:
  Bn abs() const;

  int cmp(const Bn &n) const;
  int cmp_abs(const Bn &n) const;

  int to_i();
  string to_s() const;

  void operator*=(int n);
  void operator/=(int n);

  int remainder(){ return remainder_; }
};

void
Bn::set(int val){
  sign = 1;
  if (val >= 65536) {
	values.resize(size = 2);
	values[0] = val % 65536; values[1] = val >> 16;
  } else {
	values.resize(size = 1);
	values[0] = val;
  }
}

void
Bn::set(const Bn& num){
  values.assign(num.values.begin(), num.values.end());
  sign = num.sign; size = num.size;
}

int
Bn::to_i() {
  switch(size){
    case 1:
      return sign * values[0];
    case 2:
      if (values[1]<=0x7fff)
        return sign * ((values[1]<<16) | values[0]);
      else
        ;
    default:
      return 0; // NaN
  }
}

int
Bn::cmp(const Bn &n) const {
  if(sign != n.sign) return (sign - n.sign)/2;
  return sign * cmp_abs(n);
}

int
Bn::cmp_abs(const Bn &n) const {
  if(size!=n.size)
    return size - n.size;
  for(int i=size-1;i>=0;i--)
    if(values[i]!=n.values[i]) return values[i] - n.values[i];
  return 0;
}

void
Bn::operator*=(int n){
  for(int i=0;i<size;i++) values[i]*=n;
  normalize();
}

void
Bn::operator/=(int n){
  int r = 0;
  for(int i=size-1; i>=0; i--){
    int v = (r << 16) + values[i];
    r = v % n;
    values[i] = v / n;
  }
  normalize();
  remainder_ = r;
}

void
Bn::normalize(){
  unsigned int overflown=0;
  int sz=1;
  for(int i=0;i<size;i++){
    if (values[i]>0) sz=i+1;
    if (values[i]<0) {
	  if (i==size-1) {
        sign=-sign;
        values[i]=-values[i];
        for (int j=i-1;j>=0;j--){
        }
      } else {
        // borrowable
        int b=-values[i];
        values[i+1] -= (b >> 16);
        if (b&0xffff){
          values[i+1]--;
          values[i] = 65536 - b;
        } else {
          values[i] = 0;
        }
      }
    }
    if (values[i]>=65536){
      if (i==size-1) overflown = values[i] >> 16;
      else values[i+1] += values[i] >> 16;
      values[i] %= 65536;
    }
  }
  if (overflown == 0) {
    if (sz<size) values.resize(size=sz);
    if (is_zero()) sign=1;
  } else if (overflown < 65536){
    values.resize(size+1);
    values[size++] = overflown;
  } else {
    values.resize(size+2);
    values[size++] = overflown % 65536;
    values[size++] = overflown >> 16;
  }
}

string
Bn::to_s() const {
  if (is_zero()) return "0";

  stack<char> s;
  Bn tmp(*this);
  while(!tmp.is_zero()){
    tmp /= 10;
    s.push(enc(tmp.remainder()));
  }
  stringstream ss;
  if (sign == -1) ss << "-";
  while(!s.empty()){
    ss << s.top();
    s.pop();
  }
  return ss.str();
}

int main(){
  int L=6400;
  LL a,b,c,x,k;

  cout << L << endl;
  x=0;
  for(k=1;;k++){
	a=6*k+1;if(pq(a)){
	  b=a*2-1;if(pq(b)){
		c=a+b-1;if(pq(c)){
		  Bn z(1); z*=a;z*=b;z*=c;
		  cout << z.to_s() << endl;
		  cout << 3 << " " << a << " " << b << " " << c << endl;
		  x++;
		  if (x==L) break;
		}
	  }
	}
  }
  return 0;
}