Fibonacci?

#include "bits/stdc++.h"

/*
 * Author: Matheus Monteiro
 */

using namespace std;

// #ifdef DEBUGMONTEIRO
#define _ << " , " <<
#define bug(x) cout << #x << "  >>>>>>>  " << x << endl;
// #else
// #define bug(x)
// #endif

#define int long long
#define Max(a, b) (a > b ? a : b)
#define Min(a, b) (a < b ? a : b)
#define ii pair<int, int>
#define f first
#define s second
#define vi vector<int>
#define vii vector<ii>
#define LSOne(S) ((S) & (-S))
#define UNTIL(t) while (clock() < (t) * CLOCKS_PER_SEC)
#define SZ(a) (int)a.size()
#define fastio std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);

const int MAX = 2000000; //2 * 10^5
const int MOD = 998244353; //10^9 + 7
const int OO = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-9;  //10^-9
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

int expMod(int a, int e, int m) {
    int ans = 1;
    while(e) {
        if(e & 1) ans = (ans * a) % m, e--;
        else a = (a * a) % m, e /= 2;
    }
    return ans;
}

int remainder(const string &s, int p) {
    int ans = 0;
    int pot = 1;
    for(int i = s.size() - 1; i >= 0; --i) {
        ans = (ans + ((s[i] - '0') * pot) % p) % p;
        pot = (pot * 10) % p;
    }
    return ans;
}

bool isSquareResidue(int x, int p) {
    if(x == 0) return true;
    return expMod(x, (p - 1) / 2, p) == 1;
}

bool isPerfectSquare(const string &s, int p) {
    int r = remainder(s, p);
    if(isSquareResidue((5 * r * r + 4) % p, p))
        return true;
    if(isSquareResidue((5 * r * r - 4) % p, p))
        return true;
    return false;
}

bool isPrime(int x) {
    if(x < 2) return false;
    if(x == 2) return true;
    if(x % 2 == 0) return false;
    for(int i = 2; i * i <= x; ++i) {
        if(x % i == 0) {
            return false;
        }
    }
    return true;
}

void solve() {
    string number;
    cin >> number;

    bool isFib = true;
    int numberOfTries = 30;
    int nextPrime = 2;

    while(numberOfTries--) {
        while(!isPrime(nextPrime)) ++nextPrime;
        if(isPerfectSquare(number, nextPrime) == false) isFib = false;
        nextPrime++;
    }

    cout << (isFib ? "SIM" : "NAO") << '\n';
}

int32_t main() {
    fastio;

    int t = 1;
    // std::cin >> t;
    for(int caso = 1; caso <= t; ++caso) {
        // cout << "Case #" << caso << ": ";
        solve();
    }

    return 0;
}

/*
Before submit:
    Check the corners cases
    Check solution restrictions

For implementation solutions:
    Check the flow of the variables

For intervals problems:
    Think about two pointers

For complete search:
    Think about cuts

If you get WA:
    Reread your code looking for stupid typos
    Try various manual testcases
    Recheck the correctness of your algorithm
    Reread the statement
    Write a straightforward solution, create lots of testcases by yourself, and compare both solutions
    Generate random test cases and perform a stress test, comparing your solution with the one that you are sure is correct
    Change the coder (if you're with a team)
    Give up. You may have other tasks to solve.
*/