Submission #1366676

#TimeUsernameProblemLanguageResultExecution timeMemory
1366676djangg7RUN Sequence (KAISTRUN26SPRING_B)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;

struct ret{
    int a,b,c;
};

ret mul(int a, int b, int c){
    return {a*a+b*b, a*b + b*c, b*b+c*c};
}

ret p1(int a, int b, int c){
    return {b, a + b, b + c};
}

ret fibo(int r){
    // cout << r << '\n';
    if(r == 1){
        return {0,1,1};
    }
    auto [a,b,c] = fibo(r / 2); // f1 f2 f3
    if(r % 2 == 0){
        return mul(a,b,c);
    }
    else{
        ret f = mul(a,b,c);
        return p1(f.a,f.b,f.c);
    }
}

int ans = 0;

map<int, int>mp;

signed main(){
    int n;
    int r, u;
    cin >> r >> u >> n;
    auto [a,b,c] = fibo(n - 1);
    // cout << a  << ' ' << b << ' ' << c << '\n';
    ans = r * u;
    if(n >= 100){
      cout << ans << '\n';
      return 0;
    }
    for(int i = 1; i <= r; i++){
        if((i - 1) / b != 0){
            // cout << i << '\n';
            ans -= (u - r/(u-a));
        }
    }
    cout << ans << '\n';
    
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...