結果

問題 No.3226 2×2行列累乗
ユーザー Sillpherth
提出日時 2025-08-25 15:55:40
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,040 bytes
コンパイル時間 803 ms
コンパイル使用メモリ 80,936 KB
実行使用メモリ 15,936 KB
最終ジャッジ日時 2025-08-25 15:55:45
合計ジャッジ時間 5,022 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other WA * 1 TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<stdio.h>
#include<iostream>

int main(void)
{
	int A,B,C,D,S,T,N,K,n;
	int *vecS,*vecT;
	std::cin >> A >> B >> C >> D >> S >> T >> N >> K;
	if(N==0)
	{
		std::cout << "1 1\n";
		return 0;
	}
	vecS = new int[K];
	vecT = new int[K];
	vecS[0] = (S%K+K)%K;
	vecT[0] = (T%K+K)%K;
	int index = 0;
	int cycle_len,cycle_start;
	bool cyclefound = false;
	//std::cout << vecS[0] << " " << vecT[0] << " " << N << std::endl;
	
	do
	{
		vecS[index+1] = ((A*vecS[index]+B*vecT[index])%K+K)%K;
		vecT[index+1] = ((C*vecS[index]+D*vecT[index])%K+K)%K;
		//std::cout << vecS[index+1] << " " << vecT[index+1] <<  std::endl;
		index++;
		for(int i=index-1; i>=0; i--)
		{
			if((vecS[index] == vecS[i]) && (vecT[index] == vecT[i]))
			{
				cycle_start = i;
				cycle_len = index - i;
				cyclefound = true;
				break;
			}
		}
	}while(!cyclefound);
	
	n = (N-cycle_start)%cycle_len + cycle_start;
	
	//std::cout << cycle_len << " " << N << std::endl;
	std::cout << vecS[n] << " " << vecT[n] << std::endl;
	delete[] vecS;
	delete[] vecT;
	return 0;
}
0