結果

問題 No.303 割れません
ユーザー keikei
提出日時 2018-10-08 19:11:01
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 9,002 bytes
コンパイル時間 2,523 ms
コンパイル使用メモリ 186,940 KB
実行使用メモリ 753,180 KB
最終ジャッジ日時 2024-04-20 18:40:06
合計ジャッジ時間 14,645 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
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 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:https://yukicoder.me/problems/no/303>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */
class bigint {
private:
    static const int BASE = 100000000, LEN = 8;
    bool negative;
    std::vector<int> a;
    bigint& normalize();
public:
    bigint(int x = 0);
    bigint(const std::string& s);
    bigint& operator = (const bigint& x);
    bigint& operator = (int x);
    bigint& operator = (const std::string& s);
    const bool operator < (const bigint& x) const;
    const bool operator > (const bigint& x) const;
    const bool operator <= (const bigint& x) const;
    const bool operator >= (const bigint& x) const;
    const bool operator != (const bigint& x) const;
    const bool operator == (const bigint& x) const;
    bigint operator -() const;
    bigint& operator += (const bigint& x);
    bigint& operator -= (const bigint& x);
    bigint& operator *= (const bigint& x);
    bigint& operator /= (const bigint& x);
    bigint& operator %= (const bigint& x);
    const bigint operator + (const bigint& x) const;
    const bigint operator - (const bigint& x) const;
    const bigint operator * (const bigint& x) const;
    const bigint operator / (const bigint& x) const;
    const bigint operator % (const bigint& x) const;
    friend std::pair<bigint,bigint> divmod(const bigint& lhs, const bigint& rhs);
    friend std::istream& operator >> (std::ostream& is, bigint& x); //適当実装
    friend std::ostream& operator << (std::ostream& os, const bigint& x);
    friend const bigint abs(bigint x);
};
bigint& bigint::normalize() {
    int i = a.size()-1;
    while (i >= 0 && a[i] == 0) --i;
    a.resize(i+1);
    if (a.size() == 0) negative = false;
    return *this;
}
bigint::bigint(int x) : negative(x<0) {
    x = abs(x);
    for (; x > 0; x /= BASE) a.push_back(x % BASE);
}
bigint::bigint(const std::string& s): negative(false) {
    int p = 0;
    if (s[p] == '-') { ++p; negative = true; }
    else if (s[p] == '+') { ++p; }
    for (int i = s.size()-1, v = BASE; i >= p; --i, v*=10) {
        int x = s[i]-'0';
        if (x < 0 || 9 < x) {
            std::cerr<<"error: parse error:"<<s<<std::endl;
            exit(1);
        }
        if (v == BASE) {
            v = 1;
            a.push_back(x);
        } else a.back() += (x)*v;
    }
    normalize();
}
bigint& bigint::operator = (const bigint& x) {
    negative = x.negative;
    a = x.a;
    return *this;
}
bigint& bigint::operator = (int x) { return *this = bigint(x); }
bigint& bigint::operator = (const std::string& s) { return *this = bigint(s); }
const bool bigint::operator < (const bigint& x) const {
    if (negative != x.negative) return negative < x.negative;
    if (a.size() != x.a.size()) return (a.size() < x.a.size())^negative;
    for(int i = a.size()-1; i >= 0; --i)
        if (a[i] != x.a[i]) return (a[i] < x.a[i])^negative;
    return false;
}
const bool bigint::operator > (const bigint& x) const { return x<(*this); }
const bool bigint::operator <= (const bigint& x) const { return !(x<(*this)); }
const bool bigint::operator >= (const bigint& x) const { return !((*this)<x); }
const bool bigint::operator != (const bigint& x) const { return (*this)<x || x<(*this); }
const bool bigint::operator == (const bigint& x) const { return !((*this)<x || x<(*this)); }
bigint bigint::operator -() const {
    bigint ret(*this);
    if (a.size()) ret.negative = !ret.negative;
    return ret;
}
bigint& bigint::operator += (const bigint& x) {
    if (negative != x.negative) return *this -= -x;
    if (a.size() < x.a.size()) a.resize(x.a.size());
    int tmp = 0;
    for (int i = 0; i < a.size(); ++i) {
        a[i] += (i<x.a.size()?x.a[i]:0) + tmp;
        tmp = a[i] / BASE;
        a[i] %= BASE;
    }
    if (tmp) a.push_back(1);
    return *this;
}
bigint& bigint::operator -= (const bigint& x) {
    if (negative != x.negative) return *this += -x;
    std::vector<int> b(x.a);
    if ((*this < x) ^ negative) {
        a.swap(b);
        negative = !negative;
    }
    for (int i = 0, tmp = 0; i < a.size(); ++i) {
        a[i] += BASE - (i<b.size()?b[i]:0) + tmp;
        tmp = a[i] / BASE - 1;
        a[i] %= BASE;
    }
    return this->normalize();
}
bigint& bigint::operator *= (const bigint& x) {
    negative ^= x.negative;
    std::vector<int> c(a.size()*x.a.size()+1);
    for (int i = 0; i < a.size(); ++i) {
        long long tmp = 0;
        for (int j = 0; j < x.a.size(); ++j) {
            long long v = (long long)a[i] * x.a[j] + c[i+j] + tmp;
            tmp = v / BASE;
            c[i+j] = (int)(v % BASE);
        }
        if (tmp) c[i+x.a.size()] += (int)tmp;
    }
    a.swap(c);
    return this->normalize();
}
bigint& bigint::operator /= (const bigint& x) {
    return *this = divmod(*this,x).first;
}
bigint& bigint::operator %= (const bigint& x) {
    return *this = divmod(*this,x).second;
}
const bigint bigint::operator + (const bigint& x) const {
    bigint res(*this); return res += x;
}
const bigint bigint::operator - (const bigint& x) const {
    bigint res(*this); return res -= x;
}
const bigint bigint::operator * (const bigint& x) const {
    bigint res(*this); return res *= x;
}
const bigint bigint::operator / (const bigint& x) const {
    bigint res(*this); return res /= x;
}
const bigint bigint::operator % (const bigint& x) const {
    bigint res(*this); return res %= x;
}
std::pair<bigint,bigint> divmod(const bigint& lhs, const bigint& rhs) {
    if (!rhs.a.size()) {
        std::cerr<<"error: division by zero"<<std::endl;
        exit(1);
    }
    bigint x(abs(rhs)), q, r;
    for (int i = lhs.a.size()-1; i >= 0; --i) {
        r = r * bigint::BASE + lhs.a[i];
        int head = 0, tail = bigint::BASE;
        if (r >= x) {
            while (head + 1 < tail) {
                int mid = (head + tail) / 2;
                if (x * bigint(mid) > r) tail = mid;
                else head = mid;
            }
            r -= x * head;
        }
        q.a.push_back(head);
    }
    reverse(q.a.begin(), q.a.end());
    bool neg = lhs.negative ^ lhs.negative;
    q.negative = neg; r.negative = neg;
    return std::make_pair(q.normalize(), r.normalize());
}
std::istream& operator >> (std::istream& is, bigint& x) {
    std::string tmp; is >> tmp;
    x = bigint(tmp);
    return is;
}
std::ostream& operator << (std::ostream& os, const bigint& x) {
    if (x.negative) os << '-';
    if (!x.a.size()) os << 0;
    else os << x.a.back();
    for (int i = (int)x.a.size()-2; i >= 0; --i) {
        os.width(bigint::LEN);
        os.fill('0');
        os << x.a[i];
    }
    return os;
}
const bigint abs(bigint x) {
    x.negative = false;
    return x;
}


typedef vector<bigint> vec;
typedef vector<vec> mat;

/*
 行列累乗
 X = A^M*B
 A ( N*N行列)
 
 O(N^3 logM)
 */
mat mul(mat&A,mat&B){
    mat C(A.size(),vec(B[0].size()));
    for(int i = 0; i < (int)A.size();i++){
        for(int k = 0; k < (int)B.size();k++){
            if(A[i][k] == 0) continue;
            for(int j = 0; j < B[0].size();j++){
                C[i][j] = (C[i][j] + A[i][k]*B[k][j]);
            }
        }
    }
    return C;
}

mat pow(mat A,ll n){
    mat B(A.size(),vec(A.size()));
    for(int i = 0; i < A.size();i++){
        B[i][i] = 1;
    }
    while(n > 0){
        if(n&1) B= mul(B,A);
        A = mul(A,A);
        n>>=1;
    }
    return B;
}

bigint calcfib(ll L){
    mat A(2,vec(2,1));
    A[1][1] = 0;
    return pow(A,L-1)[0][0];
}
void solve(){
    ll L; cin >> L;
    if(L == 2){
        cout << 3 << endl;
        cout << "INF" << endl;
        return;
    }
    cout << L << endl;
    if(L%2 == 1){
        cout << calcfib(L) << endl;
    }else{
        bigint fib1 = calcfib(L),fib2 = calcfib(L/2);
        fib2*=fib2;
        cout << (fib1-fib2) << endl;
    }
    
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    solve();
    return 0;
}
0