【算法】小强爱数学（迭代公式）

本文主要是介绍【算法】小强爱数学（迭代公式），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题

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

输入

第一行输入一个正整数T.表示有T组数据
接下来T行, 每行输入三个整数A,B和n
$$\begin{gathered} 1<=T<=100 \\ 0<=A,B<=1e9+7 \\ 1<=n<=1e5 \end{gathered}$$

输出

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

示例

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

分析

本题实际上就是个数学问题，积累了递推公式雀氏很好做，否则就很操蛋

递推公式
$$
\begin{aligned}

nihao
\end{aligned}
$$

KaTeX parse error: No such environment: align* at position 8: \begin{̲a̲l̲i̲g̲n̲*̲}̲ &\ 已知 A = x + …

证明
KaTeX parse error: No such environment: align* at position 8: \begin{̲a̲l̲i̲g̲n̲*̲}̲ R_{n} &\ = (x …

思路

迭代计算，类似斐波那契

代码

import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {static final int mod = 1000000000 + 7;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int T = sc.nextInt(), n;long A, B; for (int i = 0; i < T; ++i) {A = sc.nextInt(); B = sc.nextInt(); n = sc.nextInt();long[] dp = new long[n + 1];dp[1] = A % mod; dp[2] = (A * A % mod - 2 * B % mod + mod) % mod;if (n == 1) {System.out.println(dp[1]);}else if (n == 2) {System.out.println(dp[2]);}else {for (int j = 3; j <= n; ++j) {dp[j] = (A * dp[j - 1] % mod - B * dp[j - 2] % mod + mod) % mod;}System.out.println(dp[n]);}}}
}

这篇关于【算法】小强爱数学（迭代公式）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---