Fibonacci

洛谷ID: 5580
Verdict: Accepted
Submission Date: 2020-10-01
UVa Run Time: 2.80s

// Fibonacci
// Luogu ID: 5580
// Verdict: Accepted
// Submission Date: 2020-10-01
// UVa Run Time: 2.80s

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ULL;

int found = 0, K;
ULL R, MODULO[20] = {0}, POW[20], CYCLE_OF_TEN[20];

struct matrix
{
    ULL cell[2][2];
    matrix(ULL a = 0, ULL b = 0, ULL c = 0, ULL d = 0)
    {
        cell[0][0] = a, cell[0][1] = b, cell[1][0] = c, cell[1][1] = d;
    }
} one(1, 1, 1, 0), zero(0, 0, 0, 0);

// 注意防止溢出。
ULL multiplyMod (ULL a, ULL b, ULL c)
{  
    ULL r = 0;  
    for ( ; b; b >>= 1)  
    {  
        if (b & 1)  
        {  
            r += a;
            if (r >= c) r -= c;  
        }  
        a <<= 1;
        if (a >= c) a -= c;  
    }  
    return r;  
}  

matrix multiply(const matrix &a, const matrix &b, ULL MOD)
{
    matrix r;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
            {
                r.cell[i][j] += multiplyMod(a.cell[i][k], b.cell[k][j], MOD);
                r.cell[i][j] %= MOD;
            }
    return r;
}

matrix matrixPow(ULL k, ULL MOD)
{
    if (k == 0) return zero;
    if (k == 1) return one;
    matrix r = matrixPow(k >> 1, MOD);
    r = multiply(r, r, MOD);
    if (k & 1) r = multiply(r, one, MOD);
    return r;
}

void dfs(int d, ULL k)
{
    if (found) return;
    if (d == K) { R = k; found = 1; return; }
    for (int i = 0; i < 10; i++)
    {
        // 当前末 d 位已经满足条件，寻找满足末 d+1 位的 k
        ULL nextk = (k + i * CYCLE_OF_TEN[d]) % CYCLE_OF_TEN[d + 1];
        // 检查 nextk 是否符合条件
        ULL fn = matrixPow(nextk, POW[d]).cell[0][0];
        if (fn == MODULO[d]) dfs(d + 1, nextk);
    }
}

int main(int argc, char *argv[])
{
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(False);

    string S; cin >> S;
    if (stoll(S) == 0) { cout << "0\n"; return 0; }
    reverse(S.begin(), S.end());
    K = S.length();
    // MODULO[i] 表示 S 所对应的整数模 10^{i+1} 的结果
    // POW[i] 表示 10^{i+1}
    // CYCLE_OF_TEN[i] 表示 F_k 模 10^{i+1} 的最小循环节
    MODULO[0] = S[0] - '0', POW[0] = 10, CYCLE_OF_TEN[0] = 60;
    for (int i = 1; i <= K + 1; i++) POW[i] = POW[i - 1] * 10, CYCLE_OF_TEN[i] = CYCLE_OF_TEN[i - 1] * 10;
    for (int i = 1; i < K; i++) MODULO[i] = MODULO[i - 1] + (S[i] - '0') * POW[i - 1];
    // for (int i = 0; i < K; i++) cout << POW[i] << ' ' << MODULO[i] << '\n';
    // 对于个位数来说，其最小循环节为 60
    for (int k = 0; k < 60; k++) dfs(0, k);
    if (found) cout << (R + 1) << '\n';
    else cout << "NIE\n";

    return 0;
}

// Fibonacci
// Luogu ID: 5580
// Verdict: Accepted
// Submission Date: 2020-10-01
// UVa Run Time: 2.80s

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ULL;

int found = 0, K;
ULL R, MODULO[20] = {0}, POW[20], CYCLE_OF_TEN[20];

struct matrix
{
    ULL cell[2][2];
    matrix(ULL a = 0, ULL b = 0, ULL c = 0, ULL d = 0)
    {
        cell[0][0] = a, cell[0][1] = b, cell[1][0] = c, cell[1][1] = d;
    }
} one(1, 1, 1, 0), zero(0, 0, 0, 0);

// 注意防止溢出。
ULL multiplyMod (ULL a, ULL b, ULL c)
{  
    ULL r = 0;  
    for ( ; b; b >>= 1)  
    {  
        if (b & 1)  
        {  
            r += a;
            if (r >= c) r -= c;  
        }  
        a <<= 1;
        if (a >= c) a -= c;  
    }  
    return r;  
}  

matrix multiply(const matrix &a, const matrix &b, ULL MOD)
{
    matrix r;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
            {
                r.cell[i][j] += multiplyMod(a.cell[i][k], b.cell[k][j], MOD);
                r.cell[i][j] %= MOD;
            }
    return r;
}

matrix matrixPow(ULL k, ULL MOD)
{
    if (k == 0) return zero;
    if (k == 1) return one;
    matrix r = matrixPow(k >> 1, MOD);
    r = multiply(r, r, MOD);
    if (k & 1) r = multiply(r, one, MOD);
    return r;
}

void dfs(int d, ULL k)
{
    if (found) return;
    if (d == K) { R = k; found = 1; return; }
    for (int i = 0; i < 10; i++)
    {
        // 当前末 d 位已经满足条件，寻找满足末 d+1 位的 k
        ULL nextk = (k + i * CYCLE_OF_TEN[d]) % CYCLE_OF_TEN[d + 1];
        // 检查 nextk 是否符合条件
        ULL fn = matrixPow(nextk, POW[d]).cell[0][0];
        if (fn == MODULO[d]) dfs(d + 1, nextk);
    }
}

int main(int argc, char *argv[])
{
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(False);

    string S; cin >> S;
    if (stoll(S) == 0) { cout << "0\n"; return 0; }
    reverse(S.begin(), S.end());
    K = S.length();
    // MODULO[i] 表示 S 所对应的整数模 10^{i+1} 的结果
    // POW[i] 表示 10^{i+1}
    // CYCLE_OF_TEN[i] 表示 F_k 模 10^{i+1} 的最小循环节
    MODULO[0] = S[0] - '0', POW[0] = 10, CYCLE_OF_TEN[0] = 60;
    for (int i = 1; i <= K + 1; i++) POW[i] = POW[i - 1] * 10, CYCLE_OF_TEN[i] = CYCLE_OF_TEN[i - 1] * 10;
    for (int i = 1; i < K; i++) MODULO[i] = MODULO[i - 1] + (S[i] - '0') * POW[i - 1];
    // for (int i = 0; i < K; i++) cout << POW[i] << ' ' << MODULO[i] << '\n';
    // 对于个位数来说，其最小循环节为 60
    for (int k = 0; k < 60; k++) dfs(0, k);
    if (found) cout << (R + 1) << '\n';
    else cout << "NIE\n";

    return 0;
}