結果
| 問題 | No.950 行列累乗 |
| ユーザー |
 tempura_pp
|
| 提出日時 | 2019-12-10 07:07:25 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,648 bytes |
| コンパイル時間 | 2,804 ms |
| コンパイル使用メモリ | 143,832 KB |
| 実行使用メモリ | 14,740 KB |
| 最終ジャッジ日時 | 2023-09-05 23:56:13 |
| 合計ジャッジ時間 | 9,279 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
ソースコード
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
ll powmod(ll n,ll k, ll p){
ll ret=1;
while(k){
if(k&1)ret=ret*n%p;
n=n*n%p;
k>>=1;
}
return ret;
}
using mat = vector<vector<ll>>;
mat mul(mat A, mat B, ll p){
mat C(2,vector<ll>(2));
rep(i,2)rep(j,2)rep(k,2){
C[i][j]+=A[i][k]*B[k][j];
}
rep(i,2)rep(j,2)C[i][j]%=p;
return C;
}
mat powmat(mat A, ll n, ll p){
mat ret(2,vector<ll>(2));
ret[0][0]=ret[1][1]=1;
while(n){
if(n&1)ret=mul(ret,A,p);
A = mul(A,A,p);
n>>=1;
}
return ret;
}
ll calc(mat A, mat B, ll T, ll p){
ll sq = 1;
while(sq*sq<T)++sq;
map<mat,int> mp;
for(int i=sq-1;i>=0;i--){
mp[powmat(A,i,p)]=i;
}
ll ret = longinf;
rep(i,sq){
if(T-sq*i<0)break;
mat g = mul(B,powmat(A,T-sq*i,p),p);
if(mp.count(g))ret= min(ret,mp[g]+sq*i);
}
if(ret>T)return -1;
return ret;
}
ll calc2(mat A, mat B, ll T, ll p){
ll a= A[0][0], b=A[0][1], c=A[1][0], d = A[1][1];
mat P = {{b, b}, {p-a,d}};
ll inv = powmod(b*(a+d)%p, p-2, p);
mat Pi = {{d*inv%mod,(p-b)*inv%mod},{a*inv%mod, b*inv%mod}};
B = mul(P,mul(B,Pi,p),p);
if(B[0][0]||B[0][1]||B[1][0])return -1;
ll sq = 1;
while(sq*sq<T)++sq;
map<ll,int> mp;
ll x=(a+d)%p;
for(int i=sq-1;i>=0;i--){
mp[powmod(x,i,p)]=i;
}
ll ret = longinf;
rep(i,sq){
ll g = B[1][1]*powmod(x,T-sq*i,p);
if(mp.count(g))ret= min(ret,mp[g]+sq*i);
}
if(ret>T)return -1;
return ret;
}
map<int,int> fact(ll p, bool f){
ll tmp=p-1;
map<int,int>ret;
for(ll i=2;i*i<=p-1;++i){
if(tmp%i==0){
while(tmp%i==0){
ret[i]++;
tmp/=i;
}
}
}
if(tmp>1)ret[tmp]++;
tmp = p+f;
for(ll i=2;i*i<=p+1;++i){
if(tmp%i==0){
while(tmp%i==0){
ret[i]++;
tmp/=i;
}
}
}
if(tmp>1)ret[tmp]++;
return ret;
}
long long extGcd(long long a, long long b, long long &p, long long &q) {
if (b == 0) { p = 1; q = 0; return a; }
long long d = extGcd(b, a%b, q, p);
q -= a/b * p;
return d;
}
// 中国剰余定理
// リターン値を (r, m) とすると解は x ≡ r (mod. m)
// 解なしの場合は (0, -1) をリターン
pair<long long, long long> ChineseRem(long long b1, long long m1, long long b2, long long m2) {
long long p, q;
long long d = extGcd(m1, m2, p, q); // p is inv of m1/d (mod. m2/d)
if ((b2 - b1) % d != 0) return make_pair(0, -1);
long long m = m1 * (m2/d); // lcm of (m1, m2)
long long tmp = (b2 - b1) / d * p % (m2/d);
long long r = (b1 + m1 * tmp)% m;
if(r<0)r+=m;
return make_pair(r, m);
}
int main(){
ll p;
cin>>p;
mat A(2,vector<ll>(2)), B(2,vector<ll>(2));
rep(i,2)rep(j,2)cin>>A[i][j];
rep(i,2)rep(j,2)cin>>B[i][j];
if(A==B){
cout<<1<<endl;return 0;
}
ll D = (A[0][0]+A[1][1])*(A[0][0]+A[1][1])-4*(A[0][0]*A[1][1]-A[0][1]*A[1][0]);
D%=p;
if(D<0)D+=p;
if(D==0){
if((A[0][0]+A[1][1])%p==0){
if(A==B){
cout<<1<<endl;return 0;
}
else if(mul(A,A,p)==B){
cout<<2<<endl;return 0;
}
else {
cout<<-1<<endl;return 0;
}
}
else {
auto fac = fact(p,false);
mat E = powmat(A,0,p);
ll T = p*(p-1);
for(auto& e:fac){
while(e.second && powmat(A,T/e.first,p)==E){
--e.second;
T/=e.first;
}
}
vector<ll> v, r;
for(auto e:fac){
if(e.second==0)continue;
ll q = 1;
rep(i,e.second)q*=e.first;
ll res = calc(powmat(A,T/q,p),powmat(B,T/q,p),T,p);
if(res==-1){
cout<<-1<<endl;return 0;
}
v.push_back(q);r.push_back(res);
}
pair<ll,ll> ans = {0,1};
rep(i,v.size()){
ans = ChineseRem(ans.first,ans.second, r[i],v[i]);
if(ans.second==-1){
cout<<-1<<endl;return 0;
}
}
if(powmat(A,ans.first,p)!=B){
cout<<-1<<endl;return 0;
}
cout<<ans.first<<endl;return 0;
}
}
else {
if(A[0][0]*A[1][1]%p==A[1][0]*A[0][1]%p){
auto fac = fact(p,true);
ll T = (p+1)*(p-1);
mat E = powmat(A,0,T);
for(auto& e:fac){
while(e.second && powmat(A,T/e.first,p)==E){
--e.second;
T/=e.first;
}
}
vector<ll> v, r;
for(auto e:fac){
if(e.second==0)continue;
ll q = 1;
rep(i,e.second)q*=e.first;
ll res = calc2(powmat(A,T/q,p),powmat(B,T/q,p),T,p);
if(res==-1){
cout<<-1<<endl;return 0;
}
v.push_back(q);r.push_back(res);
}
pair<ll,ll> ans = {0,1};
rep(i,v.size()){
ans = ChineseRem(ans.first,ans.second, r[i],v[i]);
if(ans.second==-1){
cout<<-1<<endl;return 0;
}
}
if(powmat(A,ans.first,p)!=B){
cout<<-1<<endl;return 0;
}
cout<<ans.first<<endl;return 0;
}
else {
auto fac = fact(p,true);
mat E = powmat(A,0,p);
ll T = (p+1)*(p-1);
for(auto& e:fac){
while(e.second && powmat(A,T/e.first,p)==E){
--e.second;
T/=e.first;
}
}
vector<ll> v, r;
for(auto e:fac){
if(e.second==0)continue;
ll q = 1;
rep(i,e.second)q*=e.first;
ll res = calc(powmat(A,T/q,p),powmat(B,T/q,p),T,p);
if(res==-1){
cout<<-1<<endl;return 0;
}
v.push_back(q);r.push_back(res);
}
pair<ll,ll> ans = {0,1};
rep(i,v.size()){
ans = ChineseRem(ans.first,ans.second, r[i],v[i]);
if(ans.second==-1){
cout<<-1<<endl;return 0;
}
}
if(powmat(A,ans.first,p)!=B){
cout<<-1<<endl;return 0;
}
cout<<ans.first<<endl;return 0;
}
}
return 0;
}