結果

問題 No.303 割れません
ユーザー mamekin
提出日時 2016-02-14 14:44:03
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2,404 ms / 10,000 ms
コード長 7,719 bytes
コンパイル時間 1,517 ms
コンパイル使用メモリ 119,256 KB
実行使用メモリ 52,444 KB
最終ジャッジ日時 2024-09-22 06:28:57
合計ジャッジ時間 24,196 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#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;

class FFT
{
private:
    vector<complex<double> > v;

    void execute(const vector<complex<double> >& input, bool isInverse, vector<complex<double> >& output) const
    {
        int n = input.size();
        vector<complex<double> > x(input.begin(), input.end());
        vector<complex<double> > y(n);

        for(int h=1; h<n; h*=2){
            int w = n / h / 2;
            for(int k=0; k<h; ++k){
                complex<double> omega = polar<double>(1, (isInverse? -1:1) * M_PI * k / h);
                for(int j=0; j<w; ++j){
                    complex<double> x0 = x[2*w*k+j];
                    complex<double> x1 = x[2*w*k+j+w] * omega;
                    y[w*k+j] = x0 + x1;
                    y[w*(k+h)+j] = x0 - x1;
                }
            }
            x.swap(y);
        }
        output.swap(x);
    }
public:
    void dft(const vector<long long>& input)
    {
        if(input.size() == 0){
            v.clear();
            return;
        }
        int n = 1;
        while(n < (int)input.size())
            n *= 2;

        vector<complex<double> > x(n, 0);
        for(unsigned i=0; i<input.size(); ++i)
            x[i] = complex<double>((double)input[i], 0.0);
        execute(x, false, v);
    }
    void idft(vector<long long>& output) const
    {
        int n = v.size();
        vector<complex<double> > y;
        execute(v, true, y);

        output.resize(n);
        for(int i=0; i<n; ++i){
            double tmp = y[i].real() / n;
            if(tmp < 0)
                output[i] = (long long)(tmp - 0.5);
            else
                output[i] = (long long)(tmp + 0.5);
        }
    }
    FFT operator*(const FFT& other) const
    {
        int n = v.size();
        if(n != other.v.size())
            throw(exception());

        FFT ans;
        ans.v.resize(n);
        for(int i=0; i<n; ++i)
            ans.v[i] = v[i] * other.v[i];
        return ans;
    }
};

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();
    }
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);

        FFT p, q, r;
        p.dft(b);
        q.dft(c);
        r = p * q;

        Bigint ans;
        ans.sign = !(sign ^ x.sign);
        r.idft(ans.a);
        for(int i=0; i<2*n-1; ++i){
            ans.a[i+1] += ans.a[i] / MAX;
            ans.a[i] %= MAX;
        }
        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;
}

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

    if(len == 2){
        cout << 3 << endl << "INF" << endl;
        return 0;
    }
    
    vector<vector<Bigint> > v = {{1, 1}, {1, 0}};
    Bigint ans;
    if(len % 2 == 0){
        v = matrixPower(v, len / 2);
        ans = v[0][1] * v[0][1];
        v = matrixPower(v, 2);
        ans = v[0][1] - ans;
    }
    else{
        v = matrixPower(v, len);
        ans = v[0][1];
    }
    cout << len << endl << ans.getStr() << endl;

    return 0;
}
0