是因为这道题太水了吗，我看看的人超级少

每周一题

算法1

(牛顿等幂和公式) $O(n)$

令$f(n)=a^n+b^n$，

则有$f(n)=f(n-1)(a+b)-ab﹡f(n-2)$

证明也蛮好证的，将右边的f函数带回原来定义再展开即可。

代码不必多说，递推即可。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
long long f[51];
int main()
{
    long long s,p,n,i;//已知a+b,ab,求a^n+b^n.(s=a+b,p=ab) 
    cin>>s>>p>>n;
    f[1]=s;f[2]=s*s-2*p;
    for(i=3;i<=n;i++)f[i]=f[i-1]*s-f[i-2]*p;
    cout<<f[n];
}

算法2

(稀奇古怪的小公式) $O(nlogn)$

很多人可能会想，那我经常用的方法是将这个凑成平方啊，试一试啊！

这个还是可以的，看代码理解一下吧！！！

C++ 代码

#include<bits/stdc++.h>
using namespace std;
long long f[51];
int main()
{
    long long s,p,n,i;//已知a+b,ab,求a^n+b^n.(s=a+b,p=ab) 
    cin>>s>>p>>n;
    f[1]=s;
    for(i=2;i<=n;i++)
        if(i%2==0)f[i]=f[i/2]*f[i/2]-2*pow(p,i/2);
        else f[i]=f[i/2]*f[i/2+1]-pow(p,i/2)*s;//pow的时间复杂度是logn的，则时间复杂度是nlogn的

    cout<<f[n];
}