結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
ユーザー JashinchanJashinchan
提出日時 2022-08-25 14:55:31
言語 C
(gcc 12.3.0)
結果
WA  
実行時間 -
コード長 2,578 bytes
コンパイル時間 1,077 ms
コンパイル使用メモリ 37,888 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-04-20 23:37:56
合計ジャッジ時間 1,370 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#define _GNU_SOURCE
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <string.h>
#include <time.h>
typedef   int8_t      i8;
typedef   int16_t     i16;
typedef   int32_t     i32;
typedef   int64_t     i64;
typedef __int128_t    i128;
typedef   uint8_t     u8;
typedef   uint16_t    u16;
typedef   uint32_t    u32;
typedef   uint64_t    u64;
typedef __uint128_t   u128;
typedef   float       f32;
typedef   double      f64;
typedef   long double f80;
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define CTZ32(a) ((a) ? __builtin_ctz((a)) : (32))
#define CTZ64(a) ((a) ? __builtin_ctzll((a)) : (64))
#define CLZ32(a) ((a) ? __builtin_clz((a)) : (32))
#define CLZ64(a) ((a) ? __builtin_clzll((a)) : (64))
#define POPCNT32(a) ((a) ? __builtin_popcount((a)) : (0))
#define POPCNT64(a) ((a) ? __builtin_popcountll((a)) : (0))
#define MSB32(a) ((31) - CLZ32((a)))
#define MSB64(a) ((63) - CLZ64((a)))


int s_fast_div(int m) { return MSB32(m - 1); }
u64 x_fast_div(int m, int s) { return (((u128)1ull << (s + 64)) + m - 1) / m; }
u64 fast_div(u64 n, u64 m, int s, u64 x) { return (((u128)n * x) >> s) >> 64; }
u64 fast_mod(u64 n, u64 m, int s, u64 x) { return n - fast_div(n, m, s, x) * m; }


void matrix_mul_mod(u64 fib[2][2], const u64 M[2][2], u64 mod, int s_, u64 x_) {
    u128 f00, f01, f10, f11;
    u64 x, y, z, w;
    f00 = fib[0][0]; f01 = fib[0][1];
    f10 = fib[1][0]; f11 = fib[1][1];
    x = fast_mod(f00 * M[0][0] + f01 * M[1][0], mod, s_, x_);
    y = fast_mod(f00 * M[0][1] + f01 * M[1][1], mod, s_, x_);
    z = fast_mod(f10 * M[0][0] + f11 * M[1][0], mod, s_, x_);
    w = fast_mod(f10 * M[0][1] + f11 * M[1][1], mod, s_, x_);
    fib[0][0] = x; fib[0][1] = y;
    fib[1][0] = z; fib[1][1] = w;
}
void rec_fib(u64 fib[2][2], u64 i, u64 mod, int s_, u64 x_) {
    const u64 M[2][2] = { { 1, 1 }
                        , { 1, 0 } }; 
    if (i == 0 || i == 1)
        return;
    matrix_mul_mod(fib, fib, mod, s_, x_);
    if (i & 1)
        matrix_mul_mod(fib, M, mod, s_, x_);
}
u64 fast_fibonacci_mod(u64 i, u64 mod) {
    u64 Fib[2][2] = { { 1, 1 }
                    , { 1, 0 } };
    if (i == 0)
        return 0;
    int s_ = s_fast_div(mod);
    u64 x_ = x_fast_div(mod, s_);
    rec_fib(Fib, i - 1, mod, s_, x_);
    return Fib[0][0];
}

int main(void) {
    u64 N, M;
    scanf("%lu%lu", &N, &M);
    printf("%lu\n", fast_fibonacci_mod(N - 1, M));
    return 0;
}
0