UVA10655

· · 题解

这里介绍一种不需要使用浮点数或者复数运算的扩域快速幂做法。

我们知道，a=\frac{p+\sqrt{z}}{2}, b=\frac{p-\sqrt{z}}{2}，其中 z=p^2-4q。注意到

2^n(a^n+b^n)&=\sum_{i=0}^n{n\choose i}p^{n-i}\sqrt{z}^{i}+\sum_{i=0}^n{n\choose i}p^{n-i}\sqrt{z}^{i}(-1)^i \\ &= \sum_{i=0}^n{n\choose i}p^{n-i}\sqrt{z}^i(1+(-1)^i) \end{align*}

我们惊奇地发现，所有诸如 \sqrt{z}^{2k+1} 的项，系数中 (1+(-1)^i) 都为 0。所以，我们考虑将非负整数域扩展至如下的域：x+y\sqrt{z}，这样，最后计算出来的结果中，\sqrt{z} 一项的系数一定为 0。容易定义该域上的加法、乘法运算。但是如何处理除以 2 呢？只需要乘以它的逆元即可。题目保证答案小于 2^{63} ，但是 2^{63} 不是一个素数。注意到比 2^{63} 略大的 9223372036854775837 是一个素数，所以我们可以对它取模。

这样，我们就严谨地秒掉了这道紫题。

代码如下：

#include<bits/stdc++.h>
using namespace std;
using ll=__int128;
const ll M=9223372036854775837ull;
ll z;
ll qpow(ll a,ll p){
    ll res=1;a%=M;
    for(;p;p>>=1){
        if(p&1)res=res*a%M;
        a=a*a%M;
    }return res;
}struct LL{
    ll x,y;//x+y sqrt(z)
    LL(){}
    LL(ll x,ll y):x(x),y(y){};
    friend LL operator+(LL a,LL b){
        return LL((a.x+b.x)%M,(a.y+b.y)%M);
    }friend LL operator*(LL a,LL b){
        return LL((a.x*b.x%M+a.y*b.y%M*z%M)%M,(a.x*b.y%M+b.x*a.y%M)%M);
    }friend LL operator/(LL a,ll b){
        return LL(a.x*qpow(b,M-2)%M,a.y*qpow(b,M-2)%M);
    }
};LL qpow(LL a,ll p){
    LL res(1,0);
    for(;p;p>>=1){
        if(p&1)res=res*a;
        a=a*a;
    }return res;
}
int main(){
    int _p,_q,_n;
    while(cin>>_p>>_q>>_n){
        ll p=_p,q=_q,n=_n;
        z=p*p-4*q;
        LL a=LL(p,1),b=LL(p,M-1);
        a=a/2;b=b/2;
        LL x=qpow(a,n)+qpow(b,n);
        cout<<(long long)x.x<<endl;
    }
    return 0;
}