小强爱数学

阿里笔试题。测评地址 https://www.nowcoder.com/test/30440638/summary 第二题

小强发现当xy=B已知以及x+y=A时,能很轻易的算出x^2+y^2的值.但小强想请你在已知 A和 B的情况下,计算出x^n+y^n的值.因为这个结果可能很大,所以所有的运算都在模1e9+7下进行.

输入描述:

第一行输入一个正整数T.表示有T组数据

接下来T行,每行输入三个整数A,B和n.

1<=T<=100
0<=A,B<=1e9+7
1<=n<=1e5

输出描述:输出T行,每一行表示每组数据的结果.

输入例子1:
3
4 4 3
2 3 4
5 2 6输出例子1:
16
999999993
9009

解答

这道题最大的难点在于用long防止相乘后溢出

//an=Aan-1-Ban-2
#include
#include
using namespace std;
int A,B,n;
const int N=100010;
const int kmod=1e9+7;
long dp[N];
void cal()
{dp[0]=2,dp[1]=A;for(int i=2;i<=n;i++){dp[i]=(A*dp[i-1]%kmod-B*dp[i-2]%kmod+kmod)%kmod;}
}
int main()
{int T;scanf("%d",&T);while(T--){cin>>A>>B>>n;cal();cout<<dp[n]<<endl;}return 0;
}

可以试一下把long dp[N]换成int,就完全不能通过。

对1e9取模的好处

1. 是质数
2. 在int范围内两数相加不溢出
3. 在long范围内两数相乘不溢出。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！