結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
コンテスト
ユーザー amotoma3
提出日時 2020-05-02 13:59:52
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,678 bytes
コンパイル時間 1,915 ms
コンパイル使用メモリ 166,504 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-29 22:55:43
合計ジャッジ時間 2,407 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:1: warning: "ONLINE_JUDGE" redefined
    1 | #define ONLINE_JUDGE
      | 
<command-line>: note: this is the location of the previous definition

ソースコード

diff # 

#define ONLINE_JUDGE
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
const ll INF=1001001001;
const ll LINF=1001001001001001001;
const ll D4[]={0,1,0,-1,0};
const ll D8[]={0,1,1,0,-1,-1,1,-1,0};
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) for(ll i=0;i<(n);++i)
#define _rep3(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2)(__VA_ARGS__)
#define _repe2(i,n) for(ll i=0;i<=(n);++i)
#define _repe3(i,a,b) for(ll i=(a);i<=(b);++i)
#define repe(...) _overload3(__VA_ARGS__,_repe3,_repe2)(__VA_ARGS__)
#define _rrep2(i,n) for(ll i=(n)-1;i>=0;i--)
#define _rrep3(i,a,b) for(ll i=(b)-1;i>=(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
template<class T>
bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>
bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
template<class T>
using pq=priority_queue<T,vector<T>,greater<T>>;

void solve();

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    solve();
}

void solve(){
    ll n,m;cin>>n>>m;
    --n;

    ll a[2][2]={{1,1},{1,0}};
    ll ans[]={1,0};
    while(n){
        if(n&1){
            ll nans[2];
            rep(i,2)nans[i]=a[i][0]*ans[0]+a[i][1]*ans[1];
            rep(i,2)ans[i]=nans[i]%m;
            cerr<<n<<' '<<ans[0]<<endl;
        }
        ll na[2][2];
        memset(na,0,sizeof(na));
        rep(i,2)rep(j,2)rep(k,2)na[i][j]+=a[i][k]*a[k][j];
        rep(i,2)rep(j,2)a[i][j]=na[i][j]%m;
        n>>=1;
    }
    cout<<ans[1]<<endl;
}
0