#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include //xAOJ ///////// #define REP(i, x, n) for(int i = x; i < n; i++) #define rep(i,n) REP(i,0,n) #define P(p) cout<<(p)< ///////// typedef long long LL; typedef long double LD; typedef unsigned long long ULL; ///////// using namespace::std; ///////// ///////// inline long double dot(const valarray& A,const valarray& B ){ return ( A * B ).sum(); } inline long double norm(valarray &A ){ return sqrt( (A * A).sum() ); } //簡約ステップ /* 入力 行列g g[i] = 基底 b_i 出力 r 簡約したもの u μ(i,j) := / :(i>j) グラムシュミット係数 この係数を簡約で1/2以下にしていく 二等辺三角形、垂線底辺を2分する */ /*void computeGSO(const MatR &g, MatR &r, MatR &u) { int n = g.size(); for(int i = 0; i < n; ++ i) { for(int j = 0; j < i; ++ j){ u[i][j] = dot(g[i], r[j]) / dot(r[j],r[j]); } r[i] = g[i]; for(int j = 0; j < i; ++ j){ r[i] = r[i] - u[i][j] * r[j]; } } } */ //グラムシュミット直交化ベクトルを計算 //Gram-Schmidt orthonormalization //つまりcomputeGSO void GSO(const vector< valarray > &B, vector< valarray >& Bstar, vector< valarray >& myu ){ int N = B.size(); //半分計算する for(int i=0;i > LLL(vector< valarray >& BBB){ //B B[i]が基底b_i //long double delta = 0.5;// int N = BBB.size();//基底の数 int M = 0;//基底の次元(要素数) if( N > 0){ M = BBB[0].size(); } //グラムシュミット直交化 ベクトル Bstar[i] vector< valarray > B(N,valarray(M) ); B = BBB; vector< valarray > Bstar(N,valarray(M) ); vector< valarray > myu(N,valarray(N) ); //GSO(B,Bstar,myu); bool flag = true; for(;flag;){ flag = false; GSO(B,Bstar,myu); int i=1; while( i < N ){ for(int j=i-1; j>=0; --j){ /*if( dot( B[i]-B[j],B[i]-B[j] ) < dot( B[i],B[i] ) ){ B[i] = B[i]-B[j]; flag = true; }*/ if( abs( myu[i][j] ) > 0.5 ){ long double keisuu = floor( myu[i][j] +0.5);//切り下げ関数 B[i] = B[i] - keisuu * B[j]; myu[i][j] -= keisuu; long long cZ = (long long)keisuu; for(int k=0;k= (3/4 - μ(i,i-1)^2 )|b(i-1)|^2 */ if( dot( Bstar[i],Bstar[i]) < ((long double)3.0/4.0 - myu[i][i-1]*myu[i][i-1])* dot(Bstar[i-1],Bstar[i-1]) ) /*if( dot(Bstar[i-1],Bstar[i-1]) > dot(Bstar[i],Bstar[i])*4 ) */ { swap( B[i-1], B[i] ); swap( BBB[i-1], BBB[i] ); GSO(B,Bstar,myu); i = max( i-1, 1); }else{ ++i; } } } /*for(int i=0;i > bmp(26,vector(100001) ); ULL kake(ULL A, int n){ //A*n ULL ret=0; for(int bit=31;bit>=0;--bit){ ret = (ret + ret) % inP; if( n & (1 << bit) ){ ret = (ret + A) % inP; } } return ret; } void initbmp(){ bmp[0][0] = 1; bmp[0][1] = inB % inP; for(int i=2;i<100001;++i){ bmp[0][i] = ( bmp[0][i-1] * inB ) % inP; } ULL add; for(int i=0;i<100001;++i){ add = bmp[0][i]; bmp[0][i] = kake( bmp[0][i], 97 ); for(int j=1;j<26;++j){ bmp[j][i] = ( bmp[j-1][i] + add ) % inP; } } } ULL calH(string &str){ int len = str.size(); ULL ret = 0; for(int i=0;i &v ){ int len = v.size(); LL ret = 0; for(int i=0;i= inP ){ ret = ret % inP; } } return ret; } void show( vector &v ){ char c; int len = v.size(); for(int i=0;i > B(3,valarray(3)); B[0][0] = 1; B[0][1] = 1; B[0][2] = 1; B[1][0] = -1; B[1][1] = 0; B[1][2] = 2; B[2][0] = 3; B[2][1] = 5; B[2][2] = 6; B = LLL(B); for(int i=0;i<3;++i){ for(int j=0;j<3;++j){ cout << " " << B[i][j]; }cout << endl; } // 0 1 0 // 1 0 1 //-1 0 2 return;*/ cin >> inB >> inP; int AA,BB; AA = inB; BB = inP; initbmp(); const int Alpha = 26; int n; vector ans; bool flag; n = 16;// for(;;){ for(;;n+=4){ // cout << n << endl; vector< valarray > B(n,valarray(n) ); vector< valarray > getB(n,valarray(n) ); for(int i=0;i 1 && ans[len-1] == 0 ){ --len;//reading 0 } string S(len,'a'); string T(len,'a'); int temp; for(int i=0;i= 0 ){ //S[i]-T[i] = temp; S[i] = 'a' + temp; T[i] = 'a'; }else{ S[i] = 'a'; T[i] = 'a' - temp; } } ULL SH,TH,aH,bH; SH = calH( S ); TH = calH( T ); aH = get_hash(S,AA,BB); bH = get_hash(T,AA,BB); // cout << SH << " " << TH << endl; // cout << S << endl; // cout << T << endl; if( SH == TH ){ cout << S << endl; cout << T << endl; // cout << aH << endl; // cout << bH << endl; return; } } }//for(n=16;;n+=4) } } int main(void){ std::cin.tie(0); std::ios::sync_with_stdio(false); std::cout << std::fixed;// cout << setprecision(16);// //cpp solve(); return 0; }