import java.math.*;
import java.io.*;
//==========================================================C
//  OS(Quadratic Sieve) Main Program                        C
//  2次ふるい法javaプログラム ふるい改良1                   C
//----------------------------------------------------------C
//   1. M = (int)sqrt(N)                                    C
//        using Bsqrt                                       C
//   2. Seting the Factor Base                              C
//        Prime Table:  PTB[NP]                             C
//        Factor Base:  FTB[NB]                             C
//   3. Sieving by QS                                       C
//        Sieved Matrix: MQS[ND][NB]                        C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2008/08/15              C
//        ( Tokyo Kougei University )                       C
//        後 保範： 東京工芸大学                            C
//==========================================================C
public class TQS2{ 
public static void main (String[] args) throws Exception
 { String s;
   int k, j, IO;
   int NV[] = new int[3];
   BigInteger N, M;
   int NB, ND, NS, NP, LP;
   long t1,t2,t3,t4;
   double T1,T2,T3;
//  I/O File set
   FileInputStream fi = new FileInputStream("in.txt");
   InputStreamReader in = new InputStreamReader(fi);
   BufferedReader bin = new BufferedReader(in);
   FileOutputStream fo = new FileOutputStream("Sieve.txt");
   PrintWriter out = new PrintWriter(fo,true);
   s = bin.readLine();
   N = new BigInteger(s);
   s = bin.readLine();
   NP = Integer.parseInt(s);
   s = bin.readLine();
   LP = Integer.parseInt(s);
//  IO=0 --> 分解結果だけ出力、IO=1 --> 途中情報出力
//  IO=2 --> 行列及び分解行列出力
   s = bin.readLine();
   IO = Integer.parseInt(s);
   if(LP > 1000000) LP = 1000000;
   out.println("2次ふるい法による因数分解");
//  QS
   t1 = System.currentTimeMillis();
   QS2 q = new QS2();
   M = q.QS(N, NP, LP, NV);
   NB = NV[0];  ND = NV[1];  NS = NV[2];
   out.println("分解対象数="+N.toString()+", 平方根="
                +M.toString());
   out.println("基底="+NB+", データ="+ND+", ふるいテーブル="+
               NS+", ふるい数="+q.NOS);
   if(IO >= 1)
    { out.println("素数基底");
      for (k=0; k<NB; k++)
       { out.print(q.FTB[k]+" "); }
      out.println("");
      out.println("ふるいに使用する値, (M+S)^2-N=0 (mod P^l)");
      out.println("NO, P, P^l, S");
      for (k=0; k<NS; k++)
       { out.println(k+"  "+q.SBV[k][0]+" "+q.SBV[k][1]+" "
         +q.SBV[k][2]); } 
    }
   if(IO >= 2)
    { out.println("最終区間のふるいデータ");
      out.println("S, /f(S), (M+S)^2-N, f(S)");
      for (k=0; k<LP; k++)
       { double VL = q.STB[0][k]/q.STB[1][k];
         out.println(k+" "+VL+"  "+q.STB[0][k]+" "+q.STB[1][k]); }
      out.println("ふるい結果");
      for (k=0; k<ND; k++)
       { BigInteger S = q.MX[k];
         S = S.multiply(S);
         S = S.subtract(N);
         out.print(k+" "+q.MX[k].toString()+" "+S.toString());
         for (int i=0; i<NB; i++)
           { out.print(" "+q.MQS[k][i]); }
         out.println("");  }
    }
//  Gauss Elimination
   t2 = System.currentTimeMillis();
   int ID = q.Gauss(ND, NB);
   if(IO >=1 ) out.println("従属数="+ID);
   t3 = System.currentTimeMillis();
//  Output AM & EM
   if(IO >= 2)
    { out.println("A+E");
      for (k=0; k<ND; k++)
       { out.print(k+"  ");
         for (int i=0; i<NB; i++)
          { out.print(q.AM[k][i]+" "); }
         for (int i=0; i<ND; i++)
          { out.print(" "+q.EM[k][i]); }
         out.println("");
       }
    }
//  Factorization
   q.Factor(N, M, ND, NB, ID);
   out.println(" ");
   out.println(N.toString()+"の分解結果(約半分は自明解)");
   for (k=0; k<ID; k++)
    { out.print("k="+k+"  ");
      if(IO >= 1)
       { int NN = q.LN[k][0];
         for (j=1; j<=NN; j++)
          { out.print(q.LN[k][j]+" "); }
         out.println("");
         for (j=0; j<NB; j++)
          { out.print(q.PW[k][j]+" "); }
         out.println("");
         out.print("X="+q.FactV[k][0].toString());
         out.println(" Y="+q.FactV[k][1].toString());
       }
      out.print("P="+q.FactV[k][2].toString());
      out.println(" Q="+q.FactV[k][3].toString());
    }
   t4 = System.currentTimeMillis();
   T1 = (t4 - t1)/1000.0;
   T2 = (t2 - t1)/1000.0;
   T3 = (t3 - t2)/1000.0;
   out.println("Total="+T1+", Sieve="+T2+", Gauss="+T3);
  }
}