結果
| 問題 | No.303 割れません |
| ユーザー |
 Jashinchan
|
| 提出日時 | 2022-09-14 22:23:01 |
| 言語 | C (gcc 12.3.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 33,348 bytes |
| コンパイル時間 | 2,096 ms |
| コンパイル使用メモリ | 66,236 KB |
| 実行使用メモリ | 816,128 KB |
| 最終ジャッジ日時 | 2024-05-09 02:05:14 |
| 合計ジャッジ時間 | 4,584 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
5,248 KB |
| testcase_01 | AC | 1 ms
5,376 KB |
| testcase_02 | WA | - |
| testcase_03 | MLE | - |
| 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 | -- | - |
ソースコード
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#define _GNU_SOURCE
#include <assert.h>
#include <inttypes.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
// clang-format off
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 SWAP_REF(a, b) \
do { \
(a) ^= (b); \
(b) ^= (a); \
(a) ^= (b); \
} \
while(0);
#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) ((a) ? ((31) - __builtin_clz((a))) : (-1))
#define MSB64(a) ((a) ? ((63) - __builtin_clzll((a))) : (-1))
#define LSBit(a) ((a) & (-(a)))
#define CLSBit(a) ((a) & ((a) - (1)))
#define _ROTL32_INNER(x, l) (((x) << (l)) | ((x) >> ((-l) & (31))))
#define _ROTR32_INNER(x, r) (((x) >> (r)) | ((x) << ((-r) & (31))))
#define _ROTL64_INNER(x, l) (((x) << (l)) | ((x) >> ((-l) & (63))))
#define _ROTR64_INNER(x, r) (((x) >> (r)) | ((x) << ((-r) & (63))))
#define ROTR32(x, r) (((r) < (0)) ? (_ROTL32_INNER((x), ((u64)(-r) % (32)))) : (_ROTR32_INNER((x), ((r) % (32)))))
#define ROTL32(x, l) ROTR32((x), (-l))
#define ROTR64(x, r) (((r) < (0)) ? (_ROTL64_INNER((x), ((u64)(-r) % (64)))) : (_ROTR64_INNER((x), ((r) % (64)))))
#define ROTL64(x, l) ROTR64((x), (-l))
#define BIT_FLOOR32(a) ((a) ? (1u) << MSB32((a)) : (0))
#define BIT_FLOOR64(a) ((a) ? (1ull) << MSB64((a)) : (0))
#define BIT_CEIL32_REF(a) \
do { \
--(a); \
(a) |= (a) >> (1); \
(a) |= (a) >> (2); \
(a) |= (a) >> (4); \
(a) |= (a) >> (8); \
(a) |= (a) >> (16); \
(a)++; \
} while(0);
#define BIT_CEIL64_REF(a) \
do { \
--(a); \
(a) |= (a) >> (1); \
(a) |= (a) >> (2); \
(a) |= (a) >> (4); \
(a) |= (a) >> (8); \
(a) |= (a) >> (16); \
(a) |= (a) >> (32); \
(a)++; \
} while(0);
i32 in_i32(void) { i32 c, x = 0, f = 1; while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f; while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return f * x; }
static inline void out_i32_inner(i32 x) { if (x >= 10) out_i32_inner(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); }
void out_i32(i32 x) { if (x < 0) { putchar_unlocked('-'); x = -x; } out_i32_inner(x); }
i64 in_i64(void) { i64 c, x = 0, f = 1; while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f; while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return f * x; }
static inline void out_i64_inner(i64 x) { if (x >= 10) out_i64_inner(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); }
void out_i64(i64 x) { if (x < 0) { putchar_unlocked('-'); x = -x; } out_i64_inner(x); }
u32 in_u32(void) { u32 c, x = 0; while (c = getchar_unlocked(), c < 48 || c > 57); while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return x; }
void out_u32(u32 x) { if (x >= 10) out_u32(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); }
u64 in_u64(void) { u64 c, x = 0; while (c = getchar_unlocked(), c < 48 || c > 57); while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return x; }
void out_u64(u64 x) { if (x >= 10) out_u64(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); }
void NL(void) { putchar_unlocked('\n'); }
void SP(void) { putchar_unlocked(' '); }
void dump_i32(i32 x) { fprintf(stderr, "\033[1;36m%" PRId32 "\033[0m\n", x); }
void dump_i64(i64 x) { fprintf(stderr, "\033[1;36m%" PRId64 "\033[0m\n", x); }
void dump_u32(u32 x) { fprintf(stderr, "\033[1;36m%" PRIu32 "\033[0m\n", x); }
void dump_u64(u64 x) { fprintf(stderr, "\033[1;36m%" PRIu64 "\033[0m\n", x); }
void dump_i32_array(i32 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i == a_len - 1) { fprintf(stderr, "\033[1;36m%" PRId32 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRId32 "\033[0m ", a[i]); } } }
void dump_i64_array(i64 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i == a_len - 1) { fprintf(stderr, "\033[1;36m%" PRId64 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRId64 "\033[0m ", a[i]); } } }
void dump_u32_array(u32 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i == a_len - 1) { fprintf(stderr, "\033[1;36m%" PRIu32 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRIu32 "\033[0m ", a[i]); } } }
void dump_u64_array(u64 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i == a_len - 1) { fprintf(stderr, "\033[1;36m%" PRIu64 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRIu64 "\033[0m ", a[i]); } } }
void dump_i32_array_range(i32 *a, int a_len, int l, int r) { if (a_len <= r) { r = a_len - 1; } if (l > r) { return; } for (int i = l; i <= r; i++) { if (i == r) { fprintf(stderr, "\033[1;36m%" PRId32 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRId32 "\033[0m ", a[i]); } } }
void dump_i64_array_range(i64 *a, int a_len, int l, int r) { if (a_len <= r) { r = a_len - 1; } if (l > r) { return; } for (int i = l; i <= r; i++) { if (i == r) { fprintf(stderr, "\033[1;36m%" PRId64 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRId64 "\033[0m ", a[i]); } } }
void dump_u32_array_range(u32 *a, int a_len, int l, int r) { if (a_len <= r) { r = a_len - 1; } if (l > r) { return; } for (int i = l; i <= r; i++) { if (i == r) { fprintf(stderr, "\033[1;36m%" PRIu32 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRIu32 "\033[0m ", a[i]); } } }
void dump_u64_array_range(u64 *a, int a_len, int l, int r) { if (a_len <= r) { r = a_len - 1; } if (l > r) { return; } for (int i = l; i <= r; i++) { if (i == r) { fprintf(stderr, "\033[1;36m%" PRIu64 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRIu64 "\033[0m ", a[i]); } } }
void printb_32bit(u32 v) { u32 mask = (u32)1 << (sizeof(v) * CHAR_BIT - 1); do { putchar_unlocked(mask & v ? '1' : '0'); } while (mask >>= 1); }
void printb_64bit(u64 v) { u64 mask = (u64)1 << (sizeof(v) * CHAR_BIT - 1); do { putchar_unlocked(mask & v ? '1' : '0'); } while (mask >>= 1); }
// clang-format on
static u32 MOD = 998244353u;
static u32 TWICE = 1996488706u;
static u32 R1 = 301989884u;
static u32 R2 = 932051910u;
static u32 NI = 3296722945u;
static u32 gs[] = { 691295370u, 307583142u, 566821959u, 878217029u, 375146819u, 138254384u, 500602490u, 79119218u, 790898700u, 978335284u, 651424567u, 308706579u, 723000027u, 474797508u, 683394121u, 44141573u, 536892010u, 945865189u, 175417726u, 536169764u, 831722880u, 721458245u };
static u32 igs[] = { 306948983u, 888603487u, 138723248u, 65668869u, 842568658u, 953245971u, 195169681u, 118717521u, 792052763u, 828450244u, 908724728u, 218560432u, 628507989u, 248210924u, 566568154u, 6285593u, 82571768u, 49985074u, 225413092u, 349167278u, 61514562u, 763211248u };
static u32 r1_m32(u32 mod)
{
u32 x = 4294967295u;
x -= x / mod * mod;
return x + 1;
}
static u32 r2_m32(u32 mod)
{
u64 x = 18446744073709551615ul;
x -= x / mod * mod;
return x + 1;
}
static u32 ni_m32(u32 mod)
{
u32 ni = mod, f = 4;
while (f--) ni *= 2 - mod * ni;
return ni;
}
static u32 mr_m32(u64 a)
{
i64 z = (a >> 32) - (((u64)((u32)a * NI) * (u64)MOD) >> 32);;
return z < 0 ? z + MOD : z;
}
static u32 to_m32(u64 a)
{
return mr_m32(a * R2);
}
static u32 from_m32(u64 a)
{
u32 t = mr_m32(a) - MOD;
return t + (MOD & -(t >> 31));
}
static u32 add_m32(u32 a, u32 b)
{
a += b - TWICE;
a += TWICE & -(a >> 31);
return a;
}
static u32 sub_m32(u32 a, u32 b)
{
a -= b;
a += TWICE & -(a >> 31);
return a;
}
static u32 mul_m32(u64 a, u64 b)
{
return mr_m32(a * b);
}
static u32 pow_m32(u32 a, size_t b)
{
return b ? mul_m32(pow_m32(mul_m32(a, a), b >> 1), b & 1 ? a : R1) : R1;
}
static u32 inv_m32(u32 a)
{
a = from_m32(a);
int b = MOD, p = 1, q = 0;
while (b)
{
int c = a / b, d = a;
a = b;
b = d - c * b;
d = p;
p = q;
q = d - c * q;
}
return to_m32(p < 0 ? p + MOD : p);
}
static size_t bsf(size_t x)
{
__asm__("bsfq %0,%0":"=r"(x):"0"(x));
return x;
}
static u32 pow_mod(u32 a, size_t b)
{
return b ? (u64)pow_mod((u64)a * a % MOD, b >> 1) * (b & 1 ? a : 1) % MOD : 1;
}
static u32 primitive_root(void)
{
if (MOD == 2) return 1;
if (MOD == 167772161 || MOD == 469762049 || MOD == 998244353) return 3;
if (MOD == 754974721) return 11;
const u32 phi = MOD - 1;
u32 g = 2u, m = phi, p = 5u, q = 7u;
u32 pr[32] = {2};
size_t psz = 1;
while ((m & 1) == false) m >>= 1;
if (m == m / 3 * 3)
{
pr[psz++] = 3;
do {
m /= 3;
} while (m == m / 3 * 3);
}
while (p * p <= m)
{
if (m == m / p * p)
{
pr[psz++] = p;
do {
m /= p;
} while (m == m / p * p);
}
p += 6;
if (m == m / q * q)
{
pr[psz++] = q;
do {
m /= q;
} while (m == m / q * q);
}
q += 6;
}
if (m != 1) pr[psz++] = m;
while (true)
{
bool f = true;
for (int i = 0; i < psz; ++i)
{
if (!f) break;
f &= (pow_mod(g, phi / pr[i]) != 1);
}
if (f) return g;
++g;
}
}
static void init(const u32 mod)
{
MOD = mod;
TWICE = mod << 1;
R1 = r1_m32(MOD);
R2 = r2_m32(MOD);
NI = ni_m32(MOD);
size_t ct2 = bsf(MOD - 1);
u32 now = R1, inow = R1;
u32 es[32], ies[32];
u32 e = pow_m32(to_m32(primitive_root()), (MOD - 1) >> ct2), ie = inv_m32(e);
for (int i = 0; i < ct2 - 1; ++i)
{
es[ct2 - 2 - i] = e;
e = mul_m32(e, e);
ies[ct2 - 2 - i] = ie;
ie = mul_m32(ie, ie);
}
for (int i = 0; i < ct2 - 1; ++i)
{
gs[i] = mul_m32(es[i], now);
now = mul_m32(now, ies[i]);
igs[i] = mul_m32(ies[i], inow);
inow = mul_m32(inow, es[i]);
}
}
static void ntt(size_t h, int *A, bool inv)
{
for (int k = 0; k < h; ++k)
{
size_t ph = inv ? h - k : k + 1;
size_t w = 1 << (ph - 1);
size_t p = 1 << (h - ph);
u32 now = R1;
for (int s = 0; s < w; ++s)
{
size_t offset = s << (h - ph + 1);
for (int i = 0; i < p; ++i)
{
unsigned l = A[offset + i], r = A[offset + p + i];
if (!inv) r = mul_m32(r, now);
A[offset + i] = add_m32(l, r);
A[offset + p + i] = sub_m32(l, r);
if (inv) A[offset + p + i] = mul_m32(A[offset + p + i], now);
}
now = mul_m32(now, inv ? igs[CTZ32(~s)] : gs[CTZ32(~s)]);
}
}
if (inv)
{
unsigned inv2t = inv_m32(to_m32(1 << h));
for (int i = 0; i < (1 << h); ++i) A[i] = mul_m32(A[i], inv2t);
}
}
static void convolute(size_t a_len, size_t b_len, int *A, int *B)
{
if (!a_len || !b_len) return;
const size_t c_len = MSB64(a_len + b_len - 1) + 1;
init(998244353);
for (int i = 0; i < a_len; ++i) A[i] = to_m32(A[i]);
for (int i = 0; i < b_len; ++i) B[i] = to_m32(B[i]);
ntt(c_len, A, false);
ntt(c_len, B, false);
for (int i = 0; i < (1 << c_len); ++i) A[i] = mul_m32(A[i], B[i]);
ntt(c_len, A, true);
for (int i = 0; i < (1 << c_len); ++i) A[i] = from_m32(A[i]);
}
typedef struct
{
int *digit;
size_t len;
bool sign;
} BigInteger;
static BigInteger ToInt(char *s)
{
BigInteger b;
b.sign = (s[0] == '-');
b.len = strlen(s) - b.sign;
b.digit = (int *)malloc(b.len * sizeof(int));
for (int i = 0; i < b.len; ++i)
b.digit[i] = s[strlen(s) - 1 - i] - '0';
return b;
}
static char *ToString(BigInteger c)
{
char *ret = (char *)malloc((c.len + c.sign + 1) * sizeof(char));
if (c.sign)
{
ret[0] = '-';
if (c.len == 1 && !c.digit[0])
c.sign = false;
}
for (int i = 0; i < c.len; ++i)
ret[c.sign + i] = c.digit[c.len - 1 - i] + '0';
ret[c.sign + c.len] = 0;
c.digit = NULL;
free(c.digit);
return ret;
}
static BigInteger Carry(BigInteger fix)
{
for (int i = 0; i < fix.len - 1; ++i)
{
if (fix.digit[i] >= 10)
{
fix.digit[i + 1] += fix.digit[i] / 10;
fix.digit[i] -= fix.digit[i] / 10 * 10;
}
if (fix.digit[i] < 0)
{
fix.digit[i + 1] += (fix.digit[i] + 1) / 10 - 1;
fix.digit[i] -= (fix.digit[i] + 1) / 10 * 10 - 10;
}
}
while (fix.digit[fix.len - 1] >= 10)
{
int *p = (int *)realloc(fix.digit, (fix.len + 1) * sizeof(int));
if (p)
{
fix.digit = p;
p = NULL;
free(p);
}
fix.digit[fix.len] = fix.digit[fix.len - 1] / 10;
fix.digit[fix.len - 1] -= 10 * fix.digit[fix.len];
fix.len++;
}
while (fix.len >= 2 && fix.digit[fix.len - 1] == 0)
fix.len--;
return fix;
}
static BigInteger Zero(void)
{
BigInteger z;
z.sign = false;
z.len = 1 - z.sign;
z.digit = (int *)malloc(z.len * sizeof(int));
for (int i = 0; i < z.len; ++i)
z.digit[i] = 0;
return z;
}
static int Compare(BigInteger a, BigInteger b)
{
if (a.len > b.len)
return 1;
if (a.len < b.len)
return -1;
for (int i = 0; i < a.len; ++i)
{
if (a.digit[a.len - 1 - i] > b.digit[a.len - 1 - i])
return 1;
else if (a.digit[a.len - 1 - i] < b.digit[a.len - 1 - i])
return -1;
}
return 0;
}
static BigInteger Add(BigInteger a, BigInteger b, bool subt)
{
BigInteger sum;
sum.len = a.len > b.len ? a.len : b.len;
sum.digit = (int *)calloc(sum.len + 1, sizeof(int));
if (a.sign != b.sign)
{
if (!subt)
{
if (Compare(a, b) < 0)
{
sum.sign = b.sign;
BigInteger c = a;
a = b;
b = c;
}
else
sum.sign = a.sign;
subt=true;
}
else
{
if (a.sign)
{
sum.sign = true;
subt = false;
}
else
subt = sum.sign = false;
}
}
else
{
if (subt)
{
if (Compare(a, b) < 0)
{
sum.sign = !a.sign;
BigInteger c = a;
a = b;
b = c;
}
else
sum.sign = a.sign;
}
if (!subt)
sum.sign = a.sign;
}
for (int i = 0; i < sum.len; ++i)
{
if (!subt)
sum.digit[i] = (i < a.len ? a.digit[i] : 0) + (i < b.len ? b.digit[i] : 0);
else
sum.digit[i] = (i < a.len ? a.digit[i] : 0) - (i < b.len ? b.digit[i] : 0);
}
a.digit = NULL;
free(a.digit);
b.digit = NULL;
free(b.digit);
return Carry(sum);
}
static void Naive(size_t n, int *a, int *b, int *c)
{
for (int i = 0; i < (n << 1); ++i)
c[i] = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
c[i + j] += a[i] * b[j];
}
static void Karatsuba(size_t n, int *a, int *b, int *c)
{
if (n <= 1) return Naive(n, a, b, c);
int *ar = a, *al = a + n / 2;
int *br = b, *bl = b + n / 2;
int *asum = c + 5 * n, *bsum = c + 5 * n + n / 2;
int *d1 = c, *d2 = c + n, *d3 = c + 2 * n;
for (int i = 0; i < (n >> 1); ++i)
{
asum[i] = al[i] + ar[i];
bsum[i] = bl[i] + br[i];
}
Karatsuba(n >> 1, ar, br, d1);
Karatsuba(n >> 1, al, bl, d2);
Karatsuba(n >> 1, asum, bsum, d3);
for (int i = 0; i < n; ++i) d3[i] -= d2[i] + d1[i];
for (int i = 0; i < n; ++i) c[n / 2 + i] += d3[i];
}
static void ToomCook3(size_t n, int *a, int *b, int *c)
{
if (n <= 9) return Naive(n, a, b, c);
size_t cbrt = n / 3;
int *a_m2 = (int *)calloc(cbrt, sizeof(int));
int *a_m1 = (int *)calloc(cbrt, sizeof(int));
int *a_1 = (int *)calloc(cbrt, sizeof(int));
int *b_m2 = (int *)calloc(cbrt, sizeof(int));
int *b_m1 = (int *)calloc(cbrt, sizeof(int));
int *b_1 = (int *)calloc(cbrt, sizeof(int));
int *c_m2 = (int *)calloc(cbrt << 1, sizeof(int));
int *c_m1 = (int *)calloc(cbrt << 1, sizeof(int));
int *c_1 = (int *)calloc(cbrt << 1, sizeof(int));
int *c1 = (int *)calloc(cbrt << 1, sizeof(int));
int *c3 = (int *)calloc(cbrt << 1, sizeof(int));
for (int i = 0; i < cbrt; ++i)
{
a_m2[i] = (a[(cbrt << 1) + i] << 2) - (a[cbrt + i] << 1) + a[i];
b_m2[i] = (b[(cbrt << 1) + i] << 2) - (b[cbrt + i] << 1) + b[i];
}
for (int i = 0; i < cbrt; ++i)
{
a_m1[i] = a[(cbrt << 1) + i] - a[cbrt + i] + a[i];
b_m1[i] = b[(cbrt << 1) + i] - b[cbrt + i] + b[i];
}
for (int i = 0; i < cbrt; ++i)
{
a_1[i] = a[(cbrt << 1) + i] + a[cbrt + i] + a[i];
b_1[i] = b[(cbrt << 1) + i] + b[cbrt + i] + b[i];
}
ToomCook3(cbrt, a_m2, b_m2, c_m2);
a_m2 = NULL; free(a_m2);
b_m2 = NULL; free(b_m2);
ToomCook3(cbrt, a_m1, b_m1, c_m1);
a_m1 = NULL; free(a_m1);
b_m1 = NULL; free(b_m1);
ToomCook3(cbrt, a, b, c);
ToomCook3(cbrt, a_1, b_1, c_1);
a_1 = NULL; free(a_1);
b_1 = NULL; free(b_1);
ToomCook3(cbrt, a + (cbrt << 1), b + (cbrt << 1), c + (cbrt << 2));
for (int i = 0; i < (cbrt << 1); ++i)
{
c3[i] = -c_m2[i];
c3[i] += (c_m1[i] << 1) + c_m1[i];
c3[i] -= (c[i] << 1) + c[i];
c3[i] += c_1[i];
c3[i] += (c[(cbrt << 2) + i] << 3) + (c[(cbrt << 2) + i] << 2);
c3[i] /= 6;
}
for (int i = 0; i < (cbrt << 1); ++i)
{
c[(cbrt << 1) + i] = (c_m1[i] << 1) + c_m1[i];
c[(cbrt << 1) + i] -= (c[i] << 2) + (c[i] << 1);
c[(cbrt << 1) + i] += (c_1[i] << 1) + c_1[i];
c[(cbrt << 1) + i] -= (c[(cbrt << 2) + i] << 2) + (c[(cbrt << 2) + i] << 1);
c[(cbrt << 1) + i] /= 6;
}
for (int i = 0; i < (cbrt << 1); ++i)
{
c1[i] = c_m2[i];
c1[i] -= (c_m1[i] << 2) + (c_m1[i] << 1);
c1[i] += (c[i] << 1) + c[i];
c1[i] += (c_1[i] << 1);
c1[i] -= (c[(cbrt << 2) + i] << 3) + (c[(cbrt << 2) + i] << 2);
c1[i] /= 6;
}
c_m2 = NULL; free(c_m2);
c_m1 = NULL; free(c_m1);
c_1 = NULL; free(c_1);
for (int i = 0; i < (cbrt << 1); ++i) c[cbrt + i] += c1[i];
for (int i = 0; i < (cbrt << 1); ++i) c[3 * cbrt + i] += c3[i];
c1 = NULL; free(c1);
c3 = NULL; free(c3);
}
static BigInteger Multiply(BigInteger a, BigInteger b)
{
BigInteger prod;
prod.sign = a.sign ^ b.sign;
prod.len = a.len + b.len - 1;
a.sign = b.sign = false;
char type = prod.len < 177147 ? 2 : prod.len < 200000 ? 1 : 3;
switch (type)
{
case 1:
while (prod.len != (prod.len & -prod.len))
{
prod.len++;
}
break;
case 2:
prod.len = 1;
while (prod.len < a.len + b.len - 1)
{
prod.len *= 3;
}
break;
case 3:
prod.len = MSB64(prod.len) + 1;
prod.len = 1 << prod.len;
break;
default:
prod.len = a.len + b.len - 1;
}
int *u = (int *)calloc((type == 1 ? 6 : 1) * prod.len, sizeof(int));
int *v = (int *)calloc((type == 1 ? 6 : 1) * prod.len, sizeof(int));
int *w = (int *)calloc(((type == 1 ? 3 : 1) * prod.len) << 1, sizeof(int));
for (int i = 0; i < a.len; ++i) u[i] = a.digit[i];
for (int i = 0; i < b.len; ++i) v[i] = b.digit[i];
if (type == 1) Karatsuba(prod.len, u, v, w);
else if (type == 2) ToomCook3(prod.len, u, v, w);
else
{
for (int i = 0; i < a.len; ++i)
w[i] = a.digit[i];
convolute(a.len, b.len, w, v);
}
u = NULL; free(u);
v = NULL; free(v);
for (int i = 0; i < (prod.len - 1); ++i) if (w[i] >= 10)
{
w[i + 1] += w[i] / 10;
w[i] -= w[i] / 10 * 10;
}
prod.len = a.len + b.len;
prod.digit = (int *)calloc(prod.len, sizeof(int));
for (int i = 0; i < prod.len; ++i)
prod.digit[i] = w[i];
w = NULL; free(w);
return Carry(prod);
}
static BigInteger Power(BigInteger b, size_t r)
{
if (!r)
{
BigInteger one = Zero();
one.digit[0]++;
return one;
}
if (r == 1) return b;
if (b.digit[b.len - 1] & 1) return Multiply(b, Power(b, --r));
else
{
BigInteger c = Power(b, r >> 1);
return Multiply(c, c);
}
}
static void Primary(BigInteger a, BigInteger b, BigInteger p[2])
{
if (a.len < b.len)
{
p[0] = Zero();
p[1] = a;
return;
}
if (a.len == 1 && !a.digit[0])
{
p[0] = a;
p[1] = Zero();
return;
}
BigInteger apart, quot, r, temp;
quot.sign = r.sign = apart.sign = temp.sign = false;
quot.len = a.len - b.len;
apart.len = temp.len = b.len;
quot.digit = (int *)calloc(quot.len + 1, sizeof(int));
apart.digit = (int *)calloc(apart.len + 1, sizeof(int));
temp.digit = (int *)calloc(temp.len, sizeof(int));
for (int i = 0; i < apart.len; ++i)
apart.digit[i] = a.digit[quot.len + i];
if (Compare(apart, b) >= 0) quot.len++;
apart.digit = NULL; free(apart.digit);
if (!quot.len)
{
p[0] = Zero();
p[1] = a;
return;
}
r.len = a.len - quot.len + 1;
r.digit = (int *)calloc(r.len, sizeof(int));
for (int i = 0; i < r.len; ++i)
r.digit[i] = a.digit[quot.len - 1 + i];
temp = Carry(temp);
for (int i = 0 ; i < quot.len; ++i)
{
quot.digit[quot.len - 1 - i] = 9;
for (int j = 0; j < 9; ++j)
{
temp.digit[0] = j + 1;
if (Compare(Multiply(b, temp), r) == 1)
{
quot.digit[quot.len - 1 - i] = j;
break;
}
}
temp.digit[0] = quot.digit[quot.len - 1 - i];
r = Add(r, Multiply(b, temp), true);
if (i + 1 < quot.len)
{
if(r.len == 1 && !r.digit[0])
r.digit[0] = a.digit[quot.len - 2 - i];
else
{
for (int j = 0; j < r.len; ++j)
r.digit[r.len - j] = r.digit[r.len - j - 1];
r.digit[0] = a.digit[quot.len - 2 - i];
r.len++;
}
}
}
temp.digit = NULL; free(temp.digit);
p[0] = Carry(quot);
quot.digit = NULL; free(quot.digit);
while (r.sign)
r = Add(r, b, false);
p[1] = Carry(r);
r.digit = NULL; free(r.digit);
}
static BigInteger Over(BigInteger lhs,long divisor)
{
long remain = 0;
lhs.sign ^= (divisor < 0);
if (divisor < 0) divisor = 0 - divisor;
for (int i = 0; i < lhs.len; ++i)
{
long temp = 10 * remain + lhs.digit[lhs.len - 1 - i];
lhs.digit[lhs.len - 1 - i] = temp / divisor;
remain = temp - lhs.digit[lhs.len - 1 - i] * divisor;
}
return Carry(lhs);
}
static BigInteger ShiftRight(BigInteger, int, bool);
static BigInteger ShiftLeft(BigInteger a, int n, bool decimal)
{
if (!n) return a;
if (n < 0) return ShiftRight(a, -n, decimal);
if (a.len == 1 && !a.digit[0]) return a;
if (decimal)
{
BigInteger instead;
instead.sign = a.sign;
instead.len = a.len + n;
instead.digit = (int *)calloc(instead.len, sizeof(int));
for (int i = 0; i < instead.len; ++i)
instead.digit[instead.len - 1 - i] = i < a.len ? a.digit[a.len - 1 - i] : 0;
return Carry(instead);
}
else
{
BigInteger two = Zero();
two.digit[0] = 2;
return Multiply(a, Power(two, n));
}
return Carry(a);
}
static BigInteger ShiftRight(BigInteger a, int n, bool decimal)
{
if (!n) return a;
if (n < 0) return ShiftLeft(a, -n, decimal);
if (a.len == 1 && !a.digit[0]) return a;
BigInteger instead;
instead.sign = a.sign;
instead.len = a.len;
instead.digit = (int *)calloc(instead.len, sizeof(int));
if (decimal)
{
if ((size_t)n >= a.len)
return Zero();
for (int i = 0; i < n; ++i)
instead.digit[instead.len - 1 - i] = 0;
for (int i = 0; i < a.len - n; ++i)
instead.digit[i] = a.digit[n + i];
}
else
{
for (int i = 0; i < a.len; ++i)
instead.digit[i] = a.digit[i];
while (n > 32)
{
instead = Over(instead, 4294967296L);
n -= 32;
}
while (n > 5)
{
instead = Over(instead, 32);
n -= 5;
}
while (n--)
instead = Over(instead, 2);
}
return Carry(instead);
}
static size_t BitLength(BigInteger a)
{
BigInteger dividend;
dividend.sign = false;
dividend.len = a.len;
dividend.digit = (int *)malloc(dividend.len * sizeof(int));
for (int i = 0; i < dividend.len; ++i)
dividend.digit[i] = a.digit[i];
size_t bits = 0;
long num = 0;
while (dividend.len > 315650)
{
dividend = ShiftRight(dividend, 1 << 20, false);
bits += 1 << 20;
}
while (dividend.len > 39456)
{
dividend = ShiftRight(dividend, 1 << 17, false);
bits += 1 << 17;
}
while (dividend.len > 3082)
{
dividend = ShiftRight(dividend, (1 << 11) | (1 << 13), false);
bits += (1 << 11) | (1 << 13);
}
while (dividend.len > 308)
{
dividend = ShiftRight(dividend, 1 << 10, false);
bits += 1 << 10;
}
while (dividend.len > 38)
{
dividend = ShiftRight(dividend, 1 << 7, false);
bits += 1 << 7;
}
while (dividend.len > 9)
{
dividend = ShiftRight(dividend, 1 << 5, false);
bits += 1 << 5;
}
for (int i = 0; i < dividend.len; ++i)
{
num = (num << 3) + (num << 1) + dividend.digit[dividend.len - 1 - i];
}
dividend.digit = NULL; free(dividend.digit);
return bits + MSB64(num + !a.sign) + 1;
}
const size_t BURNIKELZIEGLERTHRESHOLD = 2;
static void D42(BigInteger, BigInteger,size_t, BigInteger*);
static void D32(BigInteger a, BigInteger b, size_t n, BigInteger c[2])
{
if (a.len < b.len)
{
c[0] = Zero();
c[1] = a;
return;
}
if (a.len == 1 && !a.digit[0])
{
c[0] = a;
c[1] = a;
return;
}
if (n < BURNIKELZIEGLERTHRESHOLD)
{
return Primary(a, b, c);
}
BigInteger aHi = ShiftRight(a, n, true);
BigInteger aTop = ShiftRight(aHi, n, true);
BigInteger bTop = ShiftRight(b, n, true);
BigInteger q, r, s;
BigInteger one = Zero();
one.digit[0] = 1;
if (Compare(aTop, bTop) < 0)
{
D42(aHi, bTop, n >> 1, c);
q = c[0];
r = c[1];
}
else
{
q = Add(ShiftLeft(one, n, true), one, true);
r = Add(Add(aHi, ShiftLeft(bTop, n, true), true), bTop, false);
}
BigInteger d = Multiply(q, Add(b, ShiftLeft(bTop, n, true), true));
s = ShiftLeft(r, n, true);
r.digit = NULL; free(r.digit);
s = Add(s, Add(a, ShiftLeft(aHi, n, true), true), false);
aTop.digit = NULL; free(aTop.digit);
bTop.digit = NULL; free(bTop.digit);
aHi.digit = NULL; free(aHi.digit);
while (Compare(s, d) < 0)
{
q = Add(q, one, true);
s = Add(s, b, false);
}
c[1] = Add(s, d, true);
d.digit = NULL; free(d.digit);
c[0] = Carry(q);
q.digit = NULL; free(q.digit);
s.digit = NULL; free(s.digit);
}
static void D42(BigInteger a, BigInteger b, size_t n, BigInteger c[2])
{
if (a.len < b.len)
{
c[0] = Zero();
c[1] = a;
return;
}
if (a.len == 1 && !a.digit[0])
{
c[0] = a;
c[1] = a;
return;
}
if (n < BURNIKELZIEGLERTHRESHOLD)
{
return Primary(a, b, c);
}
BigInteger aHi = ShiftRight(a, n, true);
D32(aHi, b, n, c);
BigInteger qHi = ShiftLeft(Carry(c[0]), n, true);
BigInteger rHi = Add(ShiftLeft(Carry(c[1]), n, true), Add(a, ShiftLeft(aHi, n, true), true), false);
aHi.digit = NULL; free(aHi.digit);
D32(rHi, b, n, c);
c[0] = Add(qHi, Carry(c[0]), false);
c[1] = Carry(c[1]);
qHi.digit = NULL; free(qHi.digit);
rHi.digit = NULL; free(rHi.digit);
}
static void BurnikelZiegler(BigInteger a, BigInteger b, BigInteger c[2])
{
if (a.len == 1 && !a.digit[0])
{
a.digit = NULL; free(a.digit);
b.digit = NULL; free(b.digit);
c[0] = c[1] = Zero();
return;
}
if (a.len < b.len)
{
b.digit = NULL; free(b.digit);
c[0] = Zero();
c[1] = a;
return;
}
if (a.len < BURNIKELZIEGLERTHRESHOLD || b.len < BURNIKELZIEGLERTHRESHOLD)
{
return Primary(a, b, c);
}
size_t sigma = 1 << MSB64(b.len - ((1ul << MSB64(b.len)) == b.len));
size_t adjust = (sigma << 1) - b.len;
size_t t = (a.len + (sigma << 1) - 1) / (sigma << 1);
a = ShiftLeft(a, adjust, true);
b = ShiftLeft(b, adjust, true);
BigInteger aHi = ShiftRight(a, (t < 2 ? 0 : t - 1) * sigma << 1, true);
BigInteger q = Zero();
BigInteger r = Add(a, ShiftLeft(aHi, (t < 2 ? 0 : t - 1) * sigma << 1, true), true);
while (t--)
{
if (aHi.len < b.len)
{
c[0] = Zero();
c[1] = aHi;
}
else
D42(aHi, b, sigma, c);
q = Add(ShiftLeft(q, sigma << 1, true), c[0], false);
aHi = ShiftLeft(c[1], sigma << 1, true);
aHi = Add(aHi, ShiftRight(r, (t < 1 ? 0 : t - 1) * sigma << 1, true), false);
r = Add(r, ShiftLeft(ShiftRight(r, (t < 1 ? 0 : t - 1) * sigma << 1, true), (t < 1 ? 0 : t - 1) * sigma << 1, true), true);
}
c[0] = Carry(q);
c[0].sign = a.sign ^ b.sign;
c[1] = ShiftRight(c[1], adjust, true);
aHi.digit = NULL; free(aHi.digit);
q.digit = NULL; free(q.digit);
r.digit = NULL; free(r.digit);
}
static BigInteger Divide(BigInteger a, BigInteger b, bool mod)
{
if (a.len == 1 && !a.digit[0])
{
a.digit = NULL; free(a.digit);
b.digit = NULL; free(b.digit);
return Zero();
}
if (a.len < b.len)
{
b.digit = NULL; free(b.digit);
a.sign = false;
return mod ? a : Zero();
}
char v = Compare(a, b);
if (!v)
{
a.digit = NULL; free(a.digit);
b.digit = NULL; free(b.digit);
BigInteger one = Zero();
one.digit[0]++;
one.sign = a.sign ^ b.sign;
return mod ? Zero() : one;
}
else if(v < 0)
{
b.sign = false;
while (a.sign)
a = Add(a, b, false);
return mod ? a : Zero();
}
BigInteger c[2];
bool sign = a.sign ^ b.sign;
a.sign = b.sign = false;
BurnikelZiegler(a, b, c);
c[0].sign = sign;
return Carry(mod ? c[1] : c[0]);
}
BigInteger Fib0, Fib1, tmp0;
void fast_doubling_fibonacci(size_t k)
{
if (k == 0)
{
Fib0 = Zero();
Fib1 = Zero();
Fib1.digit[0] = 1;
Fib1.len = 1;
Fib1.sign = 0;
return;
}
if (k == 1)
{
Fib0 = Zero();
Fib0.digit[0] = 1;
Fib0.len = 1;
Fib0.sign = 0;
Fib1 = Zero();
Fib1.digit[0] = 1;
Fib1.len = 1;
Fib1.sign = 0;
return;
}
fast_doubling_fibonacci(k >> 1);
tmp0 = Fib0;
if (k & 1)
{
Fib0 = Add(Multiply(Fib0, Fib0), Multiply(Fib1, Fib1), false);
Fib1 = Multiply(Fib1, Add(Add(Fib0, Fib0, false), Fib1, false));
}
else
{
Fib0 = Multiply(Fib0, Add(Add(Fib1, Fib1, false), Fib0, true));
Fib1 = Add(Multiply(Fib0, Fib0), Multiply(Fib1, Fib1), false);
}
}
int main(void)
{
size_t L = in_u64();
if (L == 2)
{
printf("3\nINF\n");
}
fast_doubling_fibonacci(L);
if (L & 1)
printf("%zu\n%s\n", L, ToString(Fib0));
else
printf("%zu\n%s\n", L, ToString(Add(Fib0, Multiply(tmp0, tmp0), true)));
return 0;
}