import java.math.*;
import java.io.*;
//==========================================================C
//  OS(Quadratic Sieve) Main Program                        C
//  2次ふるい法javaプログラム ふるい改良3(改良3+(4)追加)    C
//                         +  行列改良2(行列をbitで表示)    C
// 　(1) ふるいは倍精度浮動小数点を使用し、本来のふるい処理 C
//   (2) 素数基底に-1を追加                                 C
//   (3) 素数基底のh倍の素数も2個存在すればふるいで採用     C
//   (4) f(x)=x^2-Nの基底での分解方法の改良(ふるいを応用)   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
//        Used Base:    UTB[NBU]                            C
//   3. Sieving by QS                                       C
//        Sieved Matrix: MQS[ND][NBU]                       C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2008/09/30              C
//        ( Tokyo Kougei University )                       C
//        後 保範： 東京工芸大学                            C
//==========================================================C
public class TQS5{ 
public static void main (String[] args) throws Exception
 { String s;
   int k, j, IO;
   int NV[] = new int[5];
   BigInteger N, M, P, Q;
   int NB, NBS, ND, NS, NP, NPP, LP, h;
   long t1,t2,t3,t4;
   BigInteger One = new BigInteger("1");
   double T1,T2,T3;
//  I/O File set
   FileInputStream fi = new FileInputStream("data.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();
   NPP = Integer.parseInt(s);
   s = bin.readLine();
   LP = Integer.parseInt(s);
   s = bin.readLine();
   h  = Integer.parseInt(s);
   NP = NPP*h;
//  IO=0 --> 分解結果だけ出力、IO=1 --> 途中情報出力
//  IO=2 --> 行列及び分解行列出力
   s = bin.readLine();
   IO = Integer.parseInt(s);
   QS5 q = new QS5();
//  入力データの大きさチェック
   if(NP > q.szNP) NP = q.szNP;
   if(LP > q.szwk) LP = q.szwk;
   out.println("2次ふるい法による因数分解");
   out.println();
   out.println(" N=P×Qと分解する, M=sqrt(N)");
//  QS
   t1 = System.currentTimeMillis();
   M = q.QS(N, NP, LP, h, NV);
   NB = NV[0];  ND = NV[1];  NS = NV[2]; NBS = NV[3];
   out.println(" N="+N.toString());
   out.println(" M="+M.toString());
   out.println();
   int NNN = ND - NV[4]; 
   out.println(" データ数="+ND+", (1次)="+NV[4]+", (2次)="+NNN);
   int NNS = q.NBU - NV[3];
   out.println(" 基底の数="+q.NBU+", (1次)="+NV[3]+", (2次)="+NNS);
   out.println(" ふるいテーブル数="+NS+", 総ふるい数="+q.NOS);
   out.println(" 2次候補データ="+q.NH+", 2次非取得データ="+q.NNZ);
//   out.println(" 2次候補データ="+q.NH);
   out.println(" 1次素数NO="+NPP+", 2次比="+h+", 区間="+LP);
   int NBB = NB - NBS;
   out.println(" 1次基底NO="+NBS+", 2次基底NO="+NBB);
   out.println(" 1次最大素数="+q.FTB[NBS-1]+", 2次素数="+q.FTB[NB-1]);
   if(IO >= 1)
    { out.println("分解基底");
      for (k=0; k<q.NBU; k++)
       { out.print(q.UTB[k]+" "); }
      out.println("");
      out.println("分解テーブル");
      for (k=0; k<NBS; k++)
       { out.println(k+" "+q.SBF[k][0]+" "+q.SBF[k][1]); }
      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 >= 3)
    { 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]);  }
     }
   if(IO >= 2)
    { 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());
         int NOM = q.MNO[k];
         for (int i=0; i<NOM; i++)
           { out.print("  "+q.MQS[k][i][0]+" "+q.MQS[k][i][1]); }
         out.println("");  }
    }
//  Gauss Elimination
   t2 = System.currentTimeMillis();
   int ID = q.Gauss(ND, q.NBU);
   if(IO >=1 ) out.println("従属数="+ID);
   t3 = System.currentTimeMillis();
//  Output AM,VC,VP
   if(IO >= 2)
    { out.println("A+E");
      for (k=0; k<ND; k++)
       { out.print(k+"  ");
         for (int i=0; i<q.NBU; i++)
          { out.print(q.AM[k][i]+" "); }
         out.println(""); }
      out.println("VC");
      for (int i=0; i<ND; i++)
       { out.print(q.VC[i]+" "); }
      out.println("");
      out.println("VP");
      for (int i=0; i<q.NBU; i++)
       { out.print(q.VP[i]+" "); }
      out.println("");
    }
//  Factorization
   q.Factor(N, M, ND, q.NBU, ID);
   out.println(" ");
   out.println("N=P×Qの分解結果");
//  Output
   int OK = 0;   
   for (k=0; k<Math.min(ID,500); k++)
    { out.print(" "+k+"  ");
      P = q.FactV[k][2];  Q = q.FactV[k][3];
      if(P.compareTo(One)*Q.compareTo(One) == 0)
        { out.println(" 自明解"); }
      else 
        { out.print("P="+P.toString());
          out.println(" Q="+Q.toString()); 
          OK ++ ; }
    }
//  Used Time
   t4 = System.currentTimeMillis();
   T1 = (t4 - t1)/1000.0;
   T2 = (t2 - t1)/1000.0;
   T3 = (t4 - t2)/1000.0;
   out.println();
   int NG = Math.min(ID,500) - OK;
   out.println("因数分解: OK="+OK+", NG="+NG);
   System.out.println("因数分解: OK="+OK+", NG="+NG);
   out.println("計算時間(秒,Total)="+T1+", Sieve="+T2+", Gauss="+T3);
   System.out.println("計算時間="+T1);
  }
}