#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long double ld; //点は縦ベクトルで表現 //B1のx列目とB2のy列目の内積 ld IP(vector > &B1, int x, vector > &B2, int y){ ld res=0; for(int i=0;i > GS(vector > &Basis){ const int n=Basis.size(); //直交系 vector > Basis_(n,vector(n)); for(int i=0;i > &Basis,int x,vector > &Basis_,int y){ return IP(Basis,x,Basis_,y)/IP(Basis_,y,Basis_,y); } // LLLアルゴリズムで簡約基底の近似を求め,0列目を最短格子ベクトルの近似として出力 // https://en.wikipedia.org/wiki/Lenstra–Lenstra–Lovász_lattice_basis_reduction_algorithm vector LLL(vector > Basis){ const int n=Basis.size(); const ld delta=3.0L/4.0L; //最短ベクトル vector sv(n); //直交系 vector > Basis_=GS(Basis); int k=1; while(k=0;j--){ ld mu=MU(Basis,k,Basis_,j); if( abs(mu) <= 0.5L ) continue; mu=roundl(mu); for(int i=0;i= (delta-mu*mu)*IP(Basis_,k-1,Basis_,k-1)) k++; else{ for(int i=0;i>p>>b; vector tmp; vector coe; int n; for(n=4;;n++){ coe.resize(n); //基底ベクトル //解説は点を横ベクトルで表現している(?)ので転置した vector > Basis(n,vector(n,0)); for(int i=0;i > st; for(int i=-25;i<=25;i++){ bool ok=false; for(char s='a';s<='z' && !ok;s++){ for(char t='a';t<='z' && !ok;t++){ if(s-t==i){ st[i]=make_pair(s,t); ok=true; } } } } //出力 string s,t; for(int i=0;i