結果

問題 No.303 割れません
ユーザー mamekinmamekin
提出日時 2016-02-11 01:44:38
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 3,614 ms / 10,000 ms
コード長 7,694 bytes
コンパイル時間 1,629 ms
コンパイル使用メモリ 119,236 KB
実行使用メモリ 48,800 KB
最終ジャッジ日時 2024-09-22 00:22:09
合計ジャッジ時間 32,404 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 1,690 ms
25,780 KB
testcase_04 AC 3,602 ms
47,916 KB
testcase_05 AC 3,614 ms
46,972 KB
testcase_06 AC 3,552 ms
47,980 KB
testcase_07 AC 2,425 ms
48,800 KB
testcase_08 AC 2,398 ms
47,928 KB
testcase_09 AC 2,447 ms
48,084 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 3,547 ms
47,860 KB
testcase_12 AC 2,444 ms
47,792 KB
testcase_13 AC 1,959 ms
27,416 KB
testcase_14 AC 1,096 ms
26,260 KB
testcase_15 AC 880 ms
15,432 KB
testcase_16 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

static const double PI = acos(-1.0);

class Bigint
{
private:
    static const int LEN = 5;
    static const int MAX = 100000;
    vector<long long> a;
    bool sign;
    void normalize(){
        while(!a.empty() && a.back() == 0)
            a.pop_back();
        if(a.empty())
            sign = true;
    }
    Bigint(const vector<long long>& x){
        a = x;
        sign = true;
        normalize();
    }
    void dft(const vector<long long>& input, vector<complex<double> >& output) const
    {
        int n = 1;
        while(n < (int)input.size())
            n *= 2;
        vector<complex<double> > x(input.begin(), input.end());
        x.resize(n);

        for(int h=1; h<n; h*=2){
            int w = n / h / 2;
            vector<complex<double> > y = x;
            for(int k=0; k<h; ++k){
                complex<double> omega = polar<double>(1, PI * k / h);
                for(int j=0; j<w; ++j){
                    complex<double> y0 = y[2*w*k+j];
                    complex<double> y1 = y[2*w*k+j+w] * omega;
                    x[w*k+j] = y0 + y1;
                    x[w*(k+h)+j] = y0 - y1;
                }
            }
        }
        output.swap(x);
    }
    void idft(const vector<complex<double> >& input, vector<long long>& output) const
    {
        int n = 1;
        while(n < (int)input.size())
            n *= 2;
        vector<complex<double> > x(input.begin(), input.end());
        x.resize(n);

        for(int h=1; h<n; h*=2){
            int w = n / h / 2;
            vector<complex<double> > y = x;
            for(int k=0; k<h; ++k){
                complex<double> omega = polar<double>(1, - PI * k / h);
                for(int j=0; j<w; ++j){
                    complex<double> y0 = y[2*w*k+j];
                    complex<double> y1 = y[2*w*k+j+w] * omega;
                    x[w*k+j] = y0 + y1;
                    x[w*(k+h)+j] = y0 - y1;
                }
            }
        }

        output.resize(n);
        for(int i=0; i<n; ++i){
            double tmp = x[i].real() / n;
            output[i] = (long long)(tmp + 0.5);
        }
    }
public:
    Bigint(){
        sign = true;
    }
    Bigint(long long x){
        sign = (x >= 0);
        x = abs(x);
        while(x > 0){
            a.push_back(x % MAX);
            x /= MAX;
        }
    }
    Bigint(const string& s){
        sign = true;
        long long tmp = MAX;
        for(int i=s.size()-1; i>=0; --i){
            if(tmp == MAX){
                a.push_back(0);
                tmp = 1;
            }
            if('0' <= s[i] && s[i] <= '9'){
                a.back() += (s[i] - '0') * tmp;
                tmp *= 10;
            }
            else if(i == 0 && s[0] == '-'){
                sign = false;
            }
            else{
                throw(exception());
            }
        }
        normalize();
    }
    long long getNum() const{
        long long ans = 0;
        for(int i=a.size()-1; i>=0; --i){
            ans *= MAX;
            ans += a[i];
        }
        return ans * (sign? 1:-1);
    }
    string getStr() const{
        ostringstream oss;
        if(a.size() == 0)
            return "0";
        if(!sign)
            oss << '-';
        for(int i=a.size()-1; i>=0; --i){
            oss << a[i];
            oss << setw(LEN) << setfill('0');
        }
        return oss.str();
    }
    Bigint operator+(const Bigint& x) const{
        if(sign ^ x.sign){
            Bigint tmp = x;
            tmp.sign = !tmp.sign;
            return *this - tmp;
        }
        Bigint ans;
        ans.sign = sign;
        long long carry = 0;
        unsigned i = 0;
        while(i < a.size() || i < x.a.size() || carry > 0){
            if(i < a.size())
                carry += a[i];
            if(i < x.a.size())
                carry += x.a[i];
            ans.a.push_back(carry % MAX);
            carry /= MAX;
            ++ i;
        }
        return ans;
    }
    Bigint operator-(const Bigint& x) const{
        if(sign ^ x.sign){
            Bigint tmp = x;
            tmp.sign = !tmp.sign;
            return *this + tmp;
        }
        Bigint ans;
        long long carry = 0;
        unsigned i=0;
        while(i < a.size() || i < x.a.size()){
            if(i < a.size())
                carry += a[i];
            if(i < x.a.size())
                carry -= x.a[i];
            if(carry < 0){
                ans.a.push_back(MAX + carry);
                carry = -1;
            }
            else{
                ans.a.push_back(carry);
                carry = 0;
            }
            ++ i;
        }
        if(carry == -1){
            ans.sign = !ans.sign;
            for(unsigned j=0; j<ans.a.size(); ++j)
                ans.a[j] = MAX - ans.a[j] - 1;
            ++ ans.a[0];
        }
        ans.normalize();
        return ans;
    }
    Bigint operator*(const Bigint& x) const{
        vector<long long> b = a;
        vector<long long> c = x.a;
        int n = max(b.size(), c.size());
        b.resize(n * 2, 0);
        c.resize(n * 2, 0);

        vector<complex<double> > p, q;
        dft(b, p);
        dft(c, q);
        n = max(p.size(), q.size());
        vector<complex<double> > r(n);
        for(int i=0; i<n; ++i)
            r[i] = p[i] * q[i];

        Bigint ans;
        ans.sign = !(sign ^ x.sign);
        idft(r, ans.a);
        long long carry = 0;
        for(int i=0; i<n; ++i){
            ans.a[i] += carry;
            carry = ans.a[i] / MAX;
            ans.a[i] %= MAX;
        }
        if(carry > 0)
            ans.a.push_back(carry);
        ans.normalize();
        return ans;
    }
    bool operator<(const Bigint& x) const{
        if(sign ^ x.sign)
            return x.sign;
        if(a.size() != x.a.size())
            return !(sign ^ (a.size() < x.a.size()));
        for(int i=a.size()-1; i>=0; --i){
            if(a[i] != x.a[i])
                return !(sign ^ (a[i] < x.a[i]));
        }
        return false;
    }
};

// 行列の積
template <class T>
vector<vector<T> > matrixProduct(const vector<vector<T> >& x, const vector<vector<T> >& y)
{
    int a = x.size();
    int b = x[0].size();
    int c = y[0].size();
    vector<vector<T> > z(a, vector<T>(c, 0));
    for(int i=0; i<a; ++i){
        for(int j=0; j<c; ++j){
            for(int k=0; k<b; ++k){
                z[i][j] = z[i][j] + x[i][k] * y[k][j];
            }
        }
    }
    return z;
}

// 行列の累乗
template <class T>
vector<vector<T> > matrixPower(const vector<vector<T> >& x, int k)
{
    int n = x.size();
    vector<vector<T> > y(n, vector<T>(n, 0));
    for(int i=0; i<n; ++i)
        y[i][i] = 1; // 積の単位元

    vector<vector<T> > z = x;
    while(k > 0){
        if(k & 1)
            y = matrixProduct(y, z);
        z = matrixProduct(z, z);
        k >>= 1;
    }
    return y;
}

Bigint solve(int len)
{
    vector<vector<Bigint> > v = {{1, 1}, {1, 0}};
    v = matrixPower(v, len);
    return v[0][1];
}

int main()
{
    int len;
    cin >> len;

    if(len == 2){
        cout << 3 << endl << "INF" << endl;
        return 0;
    }

    Bigint ans = solve(len);
    if(len % 2 == 0){
        Bigint x = solve(len / 2);
        ans = ans - x * x;
    }
    cout << len << endl << ans.getStr() << endl;

    return 0;
}
0