結果
| 問題 | No.303 割れません |
| ユーザー |
 LayCurse
|
| 提出日時 | 2015-11-10 17:48:09 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
AC
|
| 実行時間 | 2,755 ms / 10,000 ms |
| コード長 | 24,429 bytes |
| コンパイル時間 | 2,140 ms |
| コンパイル使用メモリ | 180,736 KB |
| 実行使用メモリ | 10,624 KB |
| 最終ジャッジ日時 | 2024-10-14 17:12:57 |
| 合計ジャッジ時間 | 26,184 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,248 KB |
| testcase_02 | AC | 2 ms
5,248 KB |
| testcase_03 | AC | 945 ms
7,040 KB |
| testcase_04 | AC | 2,665 ms
10,388 KB |
| testcase_05 | AC | 2,755 ms
10,624 KB |
| testcase_06 | AC | 2,643 ms
10,496 KB |
| testcase_07 | AC | 2,073 ms
8,960 KB |
| testcase_08 | AC | 2,145 ms
9,088 KB |
| testcase_09 | AC | 2,129 ms
8,960 KB |
| testcase_10 | AC | 2 ms
5,248 KB |
| testcase_11 | AC | 2,686 ms
10,368 KB |
| testcase_12 | AC | 2,145 ms
9,088 KB |
| testcase_13 | AC | 1,414 ms
7,424 KB |
| testcase_14 | AC | 516 ms
5,376 KB |
| testcase_15 | AC | 392 ms
5,376 KB |
| testcase_16 | AC | 1 ms
5,248 KB |
コンパイルメッセージ
main.cpp: In member function ‘int bigInt::Rshift(int, unsigned int*, int, unsigned int*)’:
main.cpp:173:3: warning: no return statement in function returning non-void [-Wreturn-type]
173 | }
| ^
main.cpp: In function ‘void reader(double*)’:
main.cpp:15:29: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
15 | void reader(double *x){scanf("%lf",x);}
| ~~~~~^~~~~~~~~
main.cpp: In member function ‘bigInt& bigInt::operator*=(unsigned int)’:
main.cpp:913:13: warning: control reaches end of non-void function [-Wreturn-type]
913 | mulArray(a);
| ~~~~~~~~^~~
main.cpp: In member function ‘bigInt& bigInt::operator+=(unsigned int)’:
main.cpp:854:3: warning: control reaches end of non-void function [-Wreturn-type]
854 | }
| ^
ソースコード
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
#define ll long long
#define ull unsigned ll
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(double *x){scanf("%lf",x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w){reader(x);reader(y);reader(z);reader(w);}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(double x, char c){printf("%.15f",x);mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
template<class T, class S> void writerLn(T x, S y){writer(x,' ');writer(y,'\n');}
template<class T, class S, class U> void writerLn(T x, S y, U z){writer(x,' ');writer(y,' ');writer(z,'\n');}
template<class T> void writerArr(T x[], int n){int i;if(!n){mypc('\n');return;}rep(i,n-1)writer(x[i],' ');writer(x[n-1],'\n');}
char memarr[17000000]; void *mem = memarr;
#define MD 1000000007
struct bigInt{
int sz, mem, sign;
unsigned *d;
static void *workMemory;
static bigInt *writerbase;
inline void init(void){
mem = 0; d = NULL;
set();
}
inline void init(int x){
mem = 0; d = NULL;
set(x);
}
inline void init(unsigned x){
mem = 0; d = NULL;
set(x);
}
inline void init(bigInt &x){
mem = 0; d = NULL;
set(x);
}
inline void set(void){
sz = sign = 0;
}
inline void set(int x){
if(x==0){
set();
return;
}
sz = 1;
extend(sz);
if(x < 0){
sign *= -1;
d[0] = -((ll)x);
} else {
sign = 1;
d[0] = x;
}
}
inline void set(unsigned x){
if(x==0){
set();
return;
}
sz = 1;
extend(sz);
sign = 1;
d[0] = x;
}
inline void set(bigInt &a){
int i;
sz = a.sz;
sign = a.sign;
extend(sz);
rep(i,sz) d[i] = a[i];
}
inline unsigned& operator[](int n){
return d[n];
}
inline void extend(int k){
if(mem < k){
k = max(k+1, mem+mem/2);
d = (unsigned*) realloc(d, k*sizeof(unsigned));
mem = k;
}
}
inline void *malloc(int k, void *work){
d = (unsigned*)work;
mem = 2100000000;
return d+k;
}
bool operator==(bigInt &a){
int i;
if(sign != a.sign || sz != a.sz) return false;
rep(i,sz) if(d[i] != a.d[i]) return false;
return true;
}
bool operator<(bigInt &a){
if(sign < a.sign) return true;
if(sign > a.sign) return false;
if(sign==0) return false;
if(sign * cmp(sz, d, a.sz, a.d) == -1) return true;
return false;
}
inline int cmp(int as, unsigned a[], int bs, unsigned b[]){
if(as > bs) return 1;
if(as < bs) return -1;
int i;
for(i=as-1;i>=0;i--){
if(a[i] > b[i]) return 1;
if(a[i] < b[i]) return -1;
}
return 0;
}
inline int Lshift(int as, unsigned a[], int val, unsigned c[]){
int i, cs, d, r;
d = val / 32;
r = val % 32;
if(r){
cs = as+d+1;
c[cs-1] = 0;
for(i=as-1;i>=0;i--){
c[i+d+1] |= a[i]>>(32-r);
c[i+d] = a[i]<<r;
}
rep(i,d) c[i] = 0;
if(c[cs-1]==0) cs--;
} else {
for(i=as-1;i>=0;i--) c[i+d] = a[i];
rep(i,d) c[i] = 0;
cs = as + d;
}
return cs;
}
inline int Rshift(int as, unsigned a[], int val, unsigned c[]){
}
inline int add(int as, unsigned a[], unsigned b, unsigned r[]){
int i, rs = as;
rep(i,rs) r[i] = a[i];
rep(i,rs){
if(r[i]+b < r[i]){
r[i] += b;
b = 1;
} else {
r[i] += b;
b = 0;
}
}
if(b) r[rs++] = b;
return rs;
}
inline int add(int as, unsigned a[], unsigned b){
int i;
rep(i,as){
if(a[i]+b < a[i]){
a[i] += b;
b = 1;
} else {
a[i] += b;
b = 0;
}
}
if(b) a[as++] = b;
return as;
}
inline int sub(int as, unsigned a[], unsigned b, unsigned r[]){
int i, rs = as;
rep(i,rs) r[i] = a[i];
rep(i,rs){
if(r[i] < b){
r[i] -= b;
b = 1;
} else {
r[i] -= b;
break;
}
}
if(rs && r[rs-1]==0) rs--;
return rs;
}
inline int sub(int as, unsigned a[], unsigned b){
int i;
rep(i,as){
if(a[i] < b){
a[i] -= b;
b = 1;
} else {
a[i] -= b;
break;
}
}
if(a[as-1]==0) as--;
return as;
}
/* r=a or r=b is allowed */
inline int add(int as, unsigned a[], int bs, unsigned b[], unsigned r[], void *work){
int i, rs;
unsigned *carry = (unsigned*) work;
if(as < bs){
rs = bs + 1;
carry[0] = 0;
rep(i,as){
carry[i+1] = (a[i]+b[i] < a[i])?1:0;
r[i] = a[i] + b[i];
}
REP(i,as,bs){
carry[i+1] = 0;
r[i] = b[i];
}
r[rs-1] = 0;
rep(i,rs){
if(r[i]+carry[i] < r[i]) carry[i+1]++;
r[i] += carry[i];
}
} else {
rs = as + 1;
carry[0] = 0;
rep(i,bs){
carry[i+1] = (a[i]+b[i] < a[i])?1:0;
r[i] = a[i] + b[i];
}
REP(i,bs,as){
carry[i+1] = 0;
r[i] = a[i];
}
r[rs-1] = 0;
rep(i,rs){
if(r[i]+carry[i] < r[i]) carry[i+1]++;
r[i] += carry[i];
}
}
if(rs && r[rs-1]==0) rs--;
return rs;
}
inline int add(int as, unsigned a[], int bs, unsigned b[]){
int i;
unsigned carry;
if(as < bs){
REP(i,as,bs) a[i] = 0;
as = bs;
}
carry = 0;
rep(i,bs){
if(carry){
carry = 0;
if(a[i]+1 < a[i]) carry = 1;
a[i]++;
}
if(a[i]+b[i] < a[i]) carry = 1;
a[i] += b[i];
}
while(carry){
carry = 0;
if(i==as) a[as++] = 0;
if(a[i]+1 < a[i]) carry = 1;
a[i]++;
i++;
}
return as;
}
/* r=a or r=b is allowed */
inline int sub(int as, unsigned a[], int bs, unsigned b[], unsigned r[], void *work){
int i, rs;
unsigned *carry = (unsigned*) work;
carry[0] = 0;
rs = as;
rep(i,bs){
if(a[i] < b[i]) carry[i+1] = 1; else carry[i+1] = 0;
r[i] = a[i] - b[i];
}
REP(i,bs,as){
carry[i+1] = 0;
r[i] = a[i];
}
rep(i,as){
if(r[i] < carry[i]) carry[i+1]++;
r[i] -= carry[i];
}
while(rs && r[rs-1]==0) --rs;
return rs;
}
inline int sub(int as, unsigned a[], int bs, unsigned b[]){
int i;
unsigned carry = 0;
rep(i,bs){
if(carry){
carry = 0;
if(a[i]==0) carry = 1;
a[i]--;
}
if(a[i] < b[i]) carry = 1;
a[i] -= b[i];
}
while(carry){
carry = 0;
if(a[i]==0) carry = 1;
a[i]--;
i++;
}
while(as && a[as-1]==0) as--;
return as;
}
inline int mul(int as, unsigned a[], unsigned b, unsigned r[]){
int i;
ull tmp = 0;
rep(i,as){
tmp += (ull)b*(ull)a[i];
r[i] = tmp&0xFFFFFFFF;
tmp >>= 32;
}
if(tmp) r[as++] = tmp;
return as;
}
inline unsigned div(int as, unsigned a[], unsigned b, int &ds, unsigned d[]){
int i;
ull tmp = 0;
ds = as;
for(i=ds-1;i>=0;i--){
tmp = (tmp<<32) + a[i];
d[i] = tmp / b;
tmp %= b;
}
if(ds && d[ds-1]==0) ds--;
return tmp;
}
/* r=a is allowed, r=b is not allowed */
inline int mulSimple(int as, unsigned a[], int bs, unsigned b[], unsigned r[], void *work){
int i, j, st, ed;
ull sum, carry, tmp;
unsigned *arr = (unsigned*) work;
if(as==0 || bs==0) return 0;
rep(i,as) arr[i] = a[i];
sum = 0;
carry = 0;
rep(i,as+bs){
st = max(0, i-as+1);
ed = min(bs, i+1);
REP(j,st,ed){
tmp = (ull) arr[i-j] * b[j];
if(sum+tmp<sum) carry++;
sum += tmp;
}
r[i] = sum&0xFFFFFFFF;
sum = (carry<<32)+(sum>>32);
carry = 0;
}
as += bs;
if(r[as-1]==0) as--;
return as;
}
/* r=a is allowed, r=b is not allowed, just because this may call mulSimple */
inline int mulKaratsuba(int as, unsigned a[], int bs, unsigned b[], unsigned c[], void *work){
int i, j, k, ms, d;
unsigned *c0, *c1, *c2, *ad, *bd, carry;
int a0s, a1s, b0s, b1s, c0s, c1s, c2s, ads, bds, ac, bc, cs;
while(as && a[as-1]==0) as--;
while(bs && b[bs-1]==0) bs--;
if(as==0 || bs==0) return 0;
if((ll)as*bs < 10000){
return mulSimple(as,a,bs,b,c,work);
}
ms = max(as, bs);
d = (ms+1) / 2;
a0s = min(as, d);
a1s = as-a0s;
b0s = min(bs, d);
b1s = bs-b0s;
c0 = (unsigned*)work;
c2 = c0 + (a0s+b0s);
c1 = c2 + (a1s+b1s);
ad = c1 + (a0s+b0s+2);
bd = ad + a0s;
work = bd + b0s;
while(a0s && a[a0s-1]==0) a0s--;
while(b0s && b[b0s-1]==0) b0s--;
c0s = mulKaratsuba(a0s, a, b0s, b, c0, work);
c2s = mulKaratsuba(a1s, a+d, b1s, b+d, c2, work);
ac = cmp(a1s, a+d, a0s, a);
bc = cmp(b1s, b+d, b0s, b);
if(ac==0 || bc==0){
c1s = 0;
c1s = add(c1s, c1, c0s, c0);
c1s = add(c1s, c1, c2s, c2);
} else {
if(ac==1) ads = sub(a1s, a+d, a0s, a, ad, work);
else ads = sub(a0s, a, a1s, a+d, ad, work);
if(bc==1) bds = sub(b1s, b+d, b0s, b, bd, work);
else bds = sub(b0s, b, b1s, b+d, bd, work);
c1s = mulKaratsuba(ads, ad, bds, bd, c1, work);
if(ac+bc==0){
c1s = add(c1s, c1, c0s, c0);
c1s = add(c1s, c1, c2s, c2);
} else if(ac==1 && bc==1){
c1s = sub(c2s, c2, c1s, c1, c1, work);
c1s = add(c1s, c1, c0s, c0);
} else {
c1s = sub(c0s, c0, c1s, c1, c1, work);
c1s = add(c1s, c1, c2s, c2);
}
}
cs = as + bs;
rep(i,c0s) c[i] = c0[i];
REP(i,c0s,cs) c[i] = 0;
carry = 0;
rep(i,c1s){
if(carry){
carry = 0;
if(c[i+d] + 1 < c[i+d]) carry = 1;
c[i+d]++;
}
if(c[i+d]+c1[i] < c[i+d]) carry = 1;
c[i+d] += c1[i];
}
while(carry){
carry = 0;
if(c[i+d] + 1 < c[i+d]) carry = 1;
c[i+d]++;
i++;
}
carry = 0;
rep(i,c2s){
if(carry){
carry = 0;
if(c[i+d+d] + 1 < c[i+d+d]) carry = 1;
c[i+d+d]++;
}
if(c[i+d+d]+c2[i] < c[i+d+d]) carry = 1;
c[i+d+d] += c2[i];
}
while(carry){
carry = 0;
if(c[i+d+d] + 1 < c[i+d+d]) carry = 1;
c[i+d+d]++;
i++;
}
if(c[cs-1]==0) cs--;
return cs;
}
inline void divKaratsuba(int as, unsigned a[], int bs, unsigned b[], int &ds, unsigned d[], int &rs, unsigned r[], void *work){
int i, p, s, t, k, shi;
int w1s, r1s, bws, w0s, r0s;
unsigned cof, *w1, *r1, *bw, *w0, *r0, *aa, *bb;
while(as && a[as-1]==0) as--;
while(bs && b[bs-1]==0) bs--;
assert(bs!=0);
k = cmp(bs,b,as,a);
if(k==1){
ds = 0;
rs = as;
rep(i,rs) r[i] = a[i];
return;
}
if(bs==1){
r[0] = div(as, a, b[0], ds, d);
rs = 1;
if(!r[0]) rs=0;
return;
}
shi = max(0, as+1 - bs*2) + 1;
aa = (unsigned*)work;
bb = aa + as+shi+1;
work = bb + bs+shi;
cof = (1ULL<<32) / (b[bs-1]+1);
as = mul(as, a, cof, aa);
bs = mul(bs, b, cof, bb);
shi = max(0, as - bs*2);
if((bs+shi)%2) shi++;
if(shi > 0){
for(i=as-1;i>=0;i--) aa[i+shi] = aa[i];
rep(i,shi) aa[i] = 0;
for(i=bs-1;i>=0;i--) bb[i+shi] = bb[i];
rep(i,shi) bb[i] = 0;
as += shi;
bs += shi;
}
p = bs / 2;
s = max(0,as-2*p);
w1s = max(0, s-bs+p+1);
bws = p + w1s;
r1s = max(bs + 1, bws);
w0s = r1s-bs+p+1;
bws = max(bws, w0s+p);
r0s = max(bs+1, bws);
w1 = (unsigned*)work;
r1 = w1 + w1s;
bw = r1 + r1s;
w0 = bw + bws;
r0 = w0 + w0s;
work = r0 + r0s;
divKaratsuba(s, aa+2*p, bs-p, bb+p, w1s, w1, r1s, r1, work);
if(r1s){
rep(i,r1s) r1[i+p] = r1[i];
rep(i,p) r1[i] = 0;
r1s += p;
}
s = min(p, as-p);
r1s = add(r1s, r1, s, aa+p);
bws = mulKaratsuba(p, bb, w1s, w1, bw, work);
k = cmp(r1s, r1, bws, bw);
while(k==-1){
w1s = sub(w1s, w1, 1U);
r1s = add(r1s, r1, bs, bb);
k = cmp(r1s, r1, bws, bw);
}
if(k==1){
r1s = sub(r1s, r1, bws, bw);
} else {
r1s = 0;
}
divKaratsuba(r1s, r1, bs-p, bb+p, w0s, w0, r0s, r0, work);
if(r0s){
rep(i,r0s) r0[i+p] = r0[i];
rep(i,p) r0[i] = 0;
r0s += p;
}
r0s = add(r0s, r0, p, aa);
bws = mulKaratsuba(p, bb, w0s, w0, bw, work);
k = cmp(r0s, r0, bws, bw);
while(k==-1){
w0s = sub(w0s, w0, 1U);
r0s = add(r0s, r0, bs, bb);
k = cmp(r0s, r0, bws, bw);
}
if(k==1){
r0s = sub(r0s, r0, bws, bw);
} else {
r0s = 0;
}
ds = 0;
if(w1s){
ds = w1s + p;
rep(i,w1s) d[i+p] = w1[i];
rep(i,p) d[i] = 0;
}
ds = add(ds, d, w0s, w0);
rs = max(0, r0s - shi);
rep(i,rs) r[i] = r0[i+shi];
div(rs, r, cof, rs, r);
}
// signを無視して c = a+b
inline void addArray(bigInt &c, bigInt &a, bigInt &b){
c.sz = add(a.sz, a.d, b.sz, b.d, c.d, workMemory);
}
// signを無視して c = a-b, 仮定 a >= b
inline void subArray(bigInt &c, bigInt &a, bigInt &b){
c.sz = sub(a.sz, a.d, b.sz, b.d, c.d, workMemory);
}
// abs(a) (>,<,=) abs(b) -> (1,-1,0)
inline int ArrayCmp(bigInt &a, bigInt &b){
return cmp(a.sz, a.d, b.sz, b.d);
}
bigInt& operator+=(bigInt &a){
if(a.sign==0) return *this;
if(sign==0){ set(a); return *this; }
extend(max(sz, a.sz) + 1);
if(sign==a.sign){
addArray(*this, *this, a);
} else {
int k = ArrayCmp(*this, a);
if(k==1){
subArray(*this, *this, a);
}else if(k==-1){
subArray(*this, a, *this);
sign *= -1;
}else{
a.sign = a.sz = 0;
}
}
return *this;
}
bigInt& operator-=(bigInt &a){
if(a.sign==0) return *this;
if(sign==0){ set(a); sign*=-1; return *this; }
extend(max(sz, a.sz) + 1);
if(sign!=a.sign){
addArray(*this, *this, a);
} else {
int k = ArrayCmp(*this, a);
if(k==1){
subArray(*this, *this, a);
}else if(k==-1){
subArray(*this, a, *this);
sign *= -1;
}else{
a.sign = a.sz = 0;
}
}
return *this;
}
bigInt& operator*=(bigInt &a){
if(sign==0) return *this;
if(a.sign==0){ set(); return *this; }
extend(sz + a.sz);
sign *= a.sign;
if(this == &a){
int i;
unsigned *t = (unsigned*)workMemory;
rep(i,sz) t[i] = d[i];
sz = mulKaratsuba(sz, d, sz, t, d, t+sz);
} else {
sz = mulKaratsuba(sz, d, a.sz, a.d, d, workMemory);
}
return *this;
}
bigInt& operator/=(bigInt &a){
if(sign==0) return *this;
assert(a.sz!=0);
sign *= a.sign;
int dum;
unsigned *memory = (unsigned*)workMemory;
divKaratsuba(sz, d, a.sz, a.d, sz, d, dum, memory, memory+a.sz);
if(sz==0) sign = 0;
return *this;
}
bigInt& operator%=(bigInt &a){
if(sign==0) return *this;
assert(a.sz!=0);
sign *= a.sign;
int dum;
unsigned *memory = (unsigned*)workMemory;
divKaratsuba(sz, d, a.sz, a.d, dum, memory, sz, d, memory+max(0,sz-a.sz+1));
if(sz==0) sign = 0;
return *this;
}
void addArray(unsigned val){
int i;
rep(i,sz){
if(d[i]+val < d[i]){
d[i] += val;
val = 1;
} else {
d[i] += val;
val = 0;
break;
}
}
if(val){
extend(sz+1);
d[sz++] = val;
}
}
void subArray(unsigned val){
int i;
if(sz==1){
if(d[0] < val){
sign = -sign;
d[0] = val - d[0];
} else if(d[0] > val){
d[0] -= val;
} else {
sz = 0;
sign = 0;
}
return;
}
rep(i,sz){
if(d[i] < val){
d[i] -= val;
val = 1;
} else {
d[i] -= val;
break;
}
}
if(sz && d[sz-1]==0) sz--;
}
void mulArray(unsigned val){
int i;
ull tmp = 0;
if(val==0){
sign = sz = 0;
return;
}
if(val==1){
return;
}
extend(sz+1);
rep(i,sz){
tmp += (ull)val*(ull)d[i];
d[i] = tmp&0xFFFFFFFF;
tmp >>= 32;
}
if(tmp) d[sz++] = tmp;
}
unsigned divArray(unsigned val){
int i;
ull tmp = 0;
assert(val != 0);
if(val==1) return 0;
for(i=sz-1;i>=0;i--){
tmp = (tmp<<32) + d[i];
d[i] = tmp / val;
tmp %= val;
}
if(sz && d[sz-1]==0) sz--;
if(sz==0) sign = 0;
return tmp;
}
bigInt& operator+=(int a){
int fg;
unsigned val;
if(a==0) return *this;
if(sign==0){
set(a);
return *this;
}
if(a < 0) fg = -1, val = -((ll)a);
else fg = 1, val = a;
if(fg==sign) addArray(val);
else subArray(val);
}
bigInt& operator+=(unsigned a){
if(a==0) return *this;
if(sign==0){
set(a);
return *this;
}
if(sign==1) addArray(a);
else subArray(a);
}
bigInt& operator-=(int a){
int fg;
unsigned val;
if(a==0) return *this;
if(sign==0){
set(a);
sign *= -1;
return *this;
}
if(a < 0) fg = -1, val = -((ll)a);
else fg = 1, val = a;
if(fg!=sign) addArray(val);
else subArray(val);
}
bigInt& operator-=(unsigned a){
if(a==0) return *this;
if(sign==0){
set(a);
sign *= -1;
return *this;
}
if(sign!=1) addArray(a);
else subArray(a);
}
bigInt& operator*=(int a){
int fg;
unsigned val;
if(a==0){
sz = sign = 0;
return *this;
}
if(sign==0){
return *this;
}
if(a < 0) val = -((ll)a), sign *= -1;
else val = a;
mulArray(val);
}
bigInt& operator*=(unsigned a){
if(a==0){
sz = sign = 0;
return *this;
}
if(sign==0){
return *this;
}
mulArray(a);
}
bigInt& operator/=(int a){
int fg;
unsigned val;
assert(a!=0);
if(sign==0){
return *this;
}
if(a < 0) val = -((ll)a), sign *= -1;
else val = a;
divArray(val);
}
bigInt& operator/=(unsigned a){
assert(a!=0);
if(sign==0){
return *this;
}
divArray(a);
}
void add(bigInt &a, bigInt &b){
set(a);
(*this)+=b;
}
void sub(bigInt &a, bigInt &b){
set(a);
(*this)-=b;
}
void mul(bigInt &a, bigInt &b){
set(a);
(*this)*=b;
}
void div(bigInt &a, bigInt &b){
set(a);
(*this)/=b;
}
void mod(bigInt &a, bigInt &b){
set(a);
(*this)%=b;
}
void divmod(bigInt &a, bigInt &b, bigInt *d, bigInt *r){
assert(b.sz!=0);
d->extend(a.sz-b.sz+1);
r->extend(b.sz);
d->sign = r->sign = a.sign*b.sign;
divKaratsuba(a.sz, a.d, b.sz, b.d, d->sz, d->d, r->sz, r->d, a.workMemory);
if(d->sz==0) d->sign = 0;
if(r->sz==0) r->sign = 0;
}
void reader(int as, unsigned arr[], int &rs, unsigned r[], void *work){
int i, ss;
unsigned *s;
if(as < 300){
rs = 1;
r[0] = arr[as-1];
for(i=as-2;i>=0;i--){
rs = mul(rs, r, 1000000000U, r);
rs = add(rs, r, arr[i]);
}
return;
}
for(i=0;;i++){
if(writerbase[i].sz==0){
writerbase[i].extend(writerbase[i-1].sz * 2);
writerbase[i].sz = mulKaratsuba(writerbase[i-1].sz, writerbase[i-1].d, writerbase[i-1].sz, writerbase[i-1].d, writerbase[i].d, work);
writerbase[i].sign = 1;
}
if((1<<i) >= as) break;
}
reader(as-(1<<(i-1)), arr+(1<<(i-1)), rs, r, work);
rs = mulKaratsuba(rs, r, writerbase[i].sz, writerbase[i].d, r, work);
s = (unsigned*)work;
reader(1<<(i-1), arr, ss, s, s+(1<<(i-1)));
rs = add(rs, r, ss, s);
}
void writer(int as, unsigned a[], int d, void *work){
int i, k, bs, ts, ds;
unsigned *dis, *b, *tmp;
if(as < 100){
dis = (unsigned*)work;
b = dis + 9;
tmp = b + as;
bs = as;
rep(i,bs) b[i] = a[i];
ts = 0;
while(bs) tmp[ts++] = div(bs, b, 1000000000U, bs, b);
if(d==-1){
ds = 0;
while(tmp[ts-1]) dis[ds++] = tmp[ts-1]%10, tmp[ts-1]/=10;
for(i=ds-1;i>=0;i--) mypc(dis[i]+'0');
ts--;
} else {
i = (d - ts) * 9;
while(i>0) i--, mypc('0');
}
while(ts--){
rep(i,9) dis[i] = tmp[ts]%10, tmp[ts]/=10;
rep(i,9) mypc(dis[8-i]+'0');
}
} else {
for(i=0;;i++){
if(writerbase[i].sz==0) writerbase[i].mul(writerbase[i-1], writerbase[i-1]);
if(writerbase[i].sz*2 >= as) break;
}
b = (unsigned*)work;
tmp = b + as - writerbase[i].sz + 1;
work = tmp + writerbase[i].sz;
divKaratsuba(as, a, writerbase[i].sz, writerbase[i].d, bs, b, ts, tmp, work);
writer(bs, b, d==-1?-1:d-(1<<(i-1)), work);
writer(ts, tmp, 1<<(i-1), work);
}
}
bigInt(void){
init();
}
void free(void){
std::free(d);
}
};
void *bigInt::workMemory;
bigInt *bigInt::writerbase;
void bigIntInit(int memsize = 20){
int i;
bigInt::workMemory = malloc(memsize*1000000);
bigInt::writerbase = (bigInt*) malloc(sizeof(bigInt)*40);
bigInt::writerbase[0].init(1U);
bigInt::writerbase[1].init(1000000000U);
REP(i,2,40) bigInt::writerbase[i].init();
}
void reader(bigInt *a){
int i, j, k, sz=0, m=0;
char *buf;
unsigned *arr;
for(;;){
mygc(k);
if(k=='-'){m=1;continue;}
if('0'<=k&&k<='9'){break;}
}
buf = (char*)a->workMemory;
buf[sz++] = k - '0';
for(;;){
mygc(k);
if(k<'0' || k>'9') break;
buf[sz++] = k - '0';
}
reverse(buf,buf+sz);
arr = (unsigned*)(buf+sz);
k = sz / 9;
rep(i,k){
arr[i] = 0;
for(j=8;j>=0;j--) arr[i] = arr[i]*10 + buf[i*9+j];
}
if(sz%9){
arr[k] = 0;
for(j=sz%9-1;j>=0;j--) arr[k] = arr[k]*10 + buf[k*9+j];
k++;
}
if(k < 100){
a->set(arr[k-1]);
for(i=k-2;i>=0;i--){
(*a) *= 1000000000U;
(*a) += arr[i];
}
} else {
a->set(0);
a->extend(k);
a->sign = 1;
a->reader(k, arr, a->sz, a->d, arr+k);
}
if(m) a->sign *= -1;
}
void writer(bigInt &a, char h){
if(a.sign!=0){
if(a.sign==-1) mypc('-');
a.writer(a.sz, a.d, -1, a.workMemory);
}else{
mypc('0');
}
mypc(h);
}
void fibonacci(ull n, bigInt &b){
bigInt a,c,d,e,f;
bigInt s,t,u,p,q;
a.set(1); c.set(1); d.set(1); e.set(1);
while(n){
if(n%2){
if(n==1){
u.mul(a,e);
p.mul(b,f);
b.add(u,p);
break;
}
s.mul(a,d);
t.mul(b,e);
u.mul(a,e);
p.mul(b,f);
q.mul(c,f);
a.add(s,t);
b.add(u,p);
c.add(t,q);
}
s.mul(d,d);
t.mul(e,e);
u.mul(d,e);
p.mul(e,f);
q.mul(f,f);
d.add(s,t);
e.add(u,p);
f.add(t,q);
n/=2;
}
}
int main(){
int i, j, k, L;
bigInt a,b,c;
bigIntInit(100);
reader(&L);
assert(1 <= L && L <= 3000000);
if(L==2){
writerLn(3);
writerLn("INF");
} else {
fibonacci(L, a);
if(L%2==0){
fibonacci(L/2, b);
b *= b;
a -= b;
}
writerLn(L);
writerLn(a);
}
return 0;
}