結果
問題 | No.526 フィボナッチ数列の第N項をMで割った余りを求める |
ユーザー |
|
提出日時 | 2017-08-31 00:05:33 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,003 bytes |
コンパイル時間 | 728 ms |
コンパイル使用メモリ | 73,708 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-06 14:39:17 |
合計ジャッジ時間 | 1,266 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cmath> #include <string> #include <vector> #include <algorithm> #include <queue> #include <map> #include <functional> #include <set> #include <numeric> #include <stack> #include <utility> #include <time.h> //#include "util.h" using namespace std; typedef long long lint; typedef unsigned long long ull; typedef pair<lint, lint> Pii; #define PI 3.14159265358979323846 #define EPS 1e-6 #define MOD ((lint)1000000007) #define MIN(a,b) ((a)<(b)?(a):(b)) #define MAX(a,b) ((a)>(b)?(a):(b)) #define CHAR_BIT 8 template <typename _Ty> ostream& operator << (ostream& ostr, const vector<_Ty>& v) { if (v.empty()) { cout << "{ }"; return ostr; } cout << "{" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) { cout << ", " << *itr; } cout << "}"; return ostr; } class Mat2D { private: lint a, b; lint c, d; public: Mat2D() { a = d = 1; b = c = 0; } Mat2D(lint a, lint b, lint c, lint d) { this->a = a; this->b = b; this->c = c; this->d = d; } Mat2D(lint E) { a = E; b = 0; c = 0; d = E; } Mat2D operator* (Mat2D& obj) { return Mat2D( a * obj.a + b * obj.c, a * obj.b + b * obj.d, c * obj.a + d * obj.c, c * obj.b + d * obj.d ); } Mat2D& operator*= (Mat2D& obj) { return (*this = *this * obj); } Mat2D operator% (lint m) { return Mat2D(a % m, b % m, c % m, d % m); } Mat2D& operator%= (lint m) { return (*this = *this % m); } lint getA() { return a; } lint getB() { return b; } lint getC() { return c; } lint getD() { return d; } }; template <typename Ty> Ty bigExp(Ty n, lint p, lint m) { if (p == 0) return Ty(1); Ty ret; ret = bigExp(n, p / 2, m); ret *= ret; ret %= m; if (p % 2) return ret * n % m; else return ret; } int main() { //clock_t start, end; //start = clock(); lint N, M; cin >> N >> M; Mat2D F = Mat2D(0, 1, 1, 1); cout << bigExp(F, N - 1, M).getB() << endl; //end = clock(); //printf("%d msec.\n", end - start); return 0; }