题解【UVA10655 Contemplation! Algebra】

fjy666 · 2022-06-19 16:10:36 · 题解

题意：给定 a+b,ab，求 (a+b)^n

矩阵递推？
是的，但我今天不讲这个。
我们充分发扬人类智慧，直接解方程解出 a,b。
什么？你说 \Delta<0？
std::complex 可以搞。
然后直接快速幂就行了。
注意：一定要用 complex<long double> 这种精度最高的东西，否则就卡精度没商量。
尽管这种做法不是出题人的意思，但我还是想说：人类智慧，yyds！

//Code by fjy666
#include <bits/stdc++.h>
using namespace std;
#define _rep(i_,a_,b_) for(int i_ = a_; i_ <= b_; ++i_)
#define mid ((L+R) >> 1)
#define get(x) (((x) - 1) / kb + 1)
typedef long long ll;

int in(void) { int x; scanf("%d", &x); return x; }
ll inl(void) { ll x; scanf("%lld", &x); return x; }
using Comp = complex<long double>;

Comp fpm(Comp a, ll n) {
    Comp res = Comp(1.0, 0);
    for(;n; n >>= 1, a *= a) if(n & 1) res *= a;
    return res;
}

int main() { 
    long double p, q; ll n;
    while(3 == scanf("%Lf%Lf%lld", &p, &q, &n)) {
        //a(p-a) = q
        //-a^2+pa-q=0
        long double A = -1, B = p, C = -q;
        long double delta = B * B - 4 * A * C;
        Comp root = Comp(-B, 0);
        //(-B+sqrt(delta)) / 2A
        if(delta >= 0) root += Comp(sqrtl(delta),0);
        else root += Comp(0,sqrtl(-delta));
        root /= 2 * A;

        // printf("%.0Lf %.0Lf\n", root.real(), root.imag());
        printf("%.0Lf\n", (fpm(root, n) + fpm(Comp(p, 0) - root, n)).real());
    }   
    return 0;
}

/* 
a list of keywords 
clear empty push_back pop_back push pop top front back
emplace_back emplace push_front pop_front insert erase
find count set reset bitset map vector string multiset
first second iterator prev next deque multimap reverse
*/