首页 > 试题广场 >

小强爱数学

[编程题]小强爱数学

热度指数：5952 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

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

输入描述:

第一行输入一个正整数.表示有组数据
接下来行,每行输入三个整数,和.

输出描述:

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

示例1

输入

输出

16
999999993
9009

算法知识视频讲解

Java

超级拉布拉多

import java.util.Scanner;

public class Main {
    static int mod = 1000000007;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int groups = sc.nextInt();
        while (groups-- >0){
            long a = sc.nextInt();
            long b=  sc.nextInt();
            int n=  sc.nextInt();
            a%=mod;
            b%=mod;
            System.out.println(new Main().solve(a,b,n));
        }
    }

    long solve(long a,long b,int n){
        
        long[] dp = new long[n+1];
        dp[0]=2;
        dp[1]=a;
        dp[2]=a*a%mod-2*b%mod;
        for(int i=3;i<=n;i++){
            dp[i] = (a*(dp[i-1])%mod-b*(dp[i-2])%mod+mod)%mod;
        }
        return dp[n];
    }
}

发表于 2021-07-02 01:29:14 回复(3)