首页 > 试题广场 >

小强爱数学

[编程题]小强爱数学

热度指数：5848 时间限制：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

算法知识视频讲解

爆爆只是想帮忙

#include<bits/stdc++.h>
using namespace std;
const int ll = 1000000007;

//递推公式 f[i] = A * f[i - 1] - B * f[i - 2]
//f[i] = x ^ i + y ^ i
int helper(int A, int B, int n){
    vector<long> dp(3);
    dp[0] = 2;
    dp[1] = A;
    for(int i = 2; i <= n; i++){
        dp[2] = ((A * dp[1] % ll) - (B * dp[0] % ll) + ll) % ll;
        dp[0] = dp[1];
        dp[1] = dp[2];
    }
    return dp[2];
}

int main(){
    int count;
    cin >> count;
    while(count-- > 0){
        int A, B, n;
        cin >> A >> B >> n;
        cout << helper(A, B, n) << endl;
    }
    return 0;
}

发表于 2022-03-13 16:30:33 回复(2)

C/C++

DeeGLMath

#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int t, n;
ll a, b;
ll dp[N];
int main(){
    cin >> t;
    while(t--){
        cin >> a >> b >> n;
        dp[1] = a;
        dp[2] = ((a*a)%mod - (2*b)%mod + mod)%mod;
        if(n == 1){
            cout << a << endl;
            return 0;
        }
        if (n == 2){
            cout << dp[n] << endl;
            return 0;
        }
        for(int i=3; i<=n; i++){
            dp[i] = ((a * dp[i-1])%mod - (b * dp[i-2])%mod + mod)%mod;
        }
        cout << dp[n] << endl;
    }
    return 0;
}

标准C++解法，不多比比。

发表于 2022-03-04 15:29:47 回复(0)

牛Coding

数学问题
记 Rn = x^n + y^n, a = x + y, b = x * y

递推公式：Rn = a * Rn-1 - b * Rn-2

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<set>
#include<string>
#include<queue>
#include<math.h>
#include<time.h>
#include<sstream>
#include<map>
#include<list>
#include<iterator>
#include<stack>
#include<thread>
using namespace std;

/*
1
2 3 4
*/
class Solution {
private:
	static const int mod = 1e9 + 7;
	int a, b, n;
	void solve() {
		long long r0 = a, r1 = (a * a % mod - 2 * b % mod + mod) % mod;
		long long r2;
		n -= 2;
		while (n) {
			r2 = (a * r1 % mod - b * r0 % mod + mod) % mod;
			r0 = r1, r1 = r2;
			--n;
		}
		cout << r1 << endl;
	}
public:
	Solution() {
		int t;
		cin >> t;
		while (t) {
			cin >> a >> b >> n;
			a %= mod, b %= mod;
			solve();
			--t;
		}
	}
};

int main() {
	Solution s;
	return 0;
}

发表于 2021-05-24 08:56:59 回复(0)

牛客576990316号

根据规律进行递归，也可以把结果存入数组或变量之中，后面进行更新

发表于 2021-08-04 23:26:54 回复(0)

pein531

题目避开了n=0的说明，其实n=0时x⁰+y⁰=2，假设f(n)=xⁿ+yⁿ，试两个n能够发现规律：

x²+y²=(x+y)²-2xy=A*(x+y)-B*2，其实就是f(2)=Af(1)-Bf(0)，接下来强行去凑这个结构
x³+y³=(x+y)³-3x²y-3xy² = (x+y)*(x²+y²+2xy)-3x²y-3xy²=(x+y)(x²+y²)+2x²y+2xy²-3x²y-3xy²=A*(x²+y²)-B*(x+y)=A*f(2)-B*f(1)

到这里就可以类似斐波那契数列那么求解了，第i项依赖前面两项。但这个数据量给爷整跪了，为了避免思考数据类型溢出用了python，结果超时。然后改用java抠这个溢出的边界

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    static final int MOD = 1000000007;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while(T-- > 0){
            String[] params = br.readLine().split(" ");
            int A = Integer.parseInt(params[0]);
            int B = Integer.parseInt(params[1]);
            int n = Integer.parseInt(params[2]);
            if(n == 1){
                System.out.println(A);
            }else if(n == 2){
                System.out.println(A*A - 2*B);
            }else{
                long dp1 = 2L, dp2 = (long)A, dp = 0L;
                for(int i = 2; i <= n; i++){
                    // 注意相减之后可能越界，加上个MOD防止溢出
                    dp = ((A * dp2) % MOD - (B * dp1) % MOD + MOD) % MOD;
                    dp1 = dp2;
                    dp2 = dp;
                }
                System.out.println(dp);
            }
        }
    }
}

编辑于 2021-11-23 15:09:07 回复(4)

聪明的托尼拒绝pua

"""
得到递归规律后，使用矩阵快速幂求解，注意python里负数的取余结果就行
"""
MOD = int(1e9+7)
 
def two_num_pow_sum(a, b, n):
    if n == 1:
        return a
    matrix=[[a, -b], [1, 0]]
    res = matrix_pow(matrix, n - 1)
    return (res[0][0] * a + res[0][1] * 2 ) % MOD
 
def matrix_pow(matrix, n):
    ans = [[1, 0], [0, 1]]
    while n > 0:
        if n & 1 != 0:
            ans = matrix_mul(ans, matrix)
        n >>= 1
        matrix = matrix_mul(matrix, matrix)
    return ans
 
def matrix_mul(ma, mb):
     
    ans = [[0] * 2 for _ in range(2)]
    for i in range(2):
        for j in range(2):
            ans[i][j] = ma[i][0] * mb[0][j] + ma[i][1] * mb[1][j]
            if ans[i][j]>=0:
                ans[i][j] %= MOD
            else:
                ans[i][j] = - (abs(ans[i][j]) % MOD)
    return ans
 
while True:
    try:
        t = int(input())
        ans = []
        for i in range(t):
            a, b, n = list(map(int, input().split()))
            ans.append(two_num_pow_sum(a, b, n))
        for num in ans:
            print(num)
    except:
        break

发表于 2022-03-12 16:09:37 回复(1)

风景旧曾谙！

没想到T*n的算法复杂度居然能过，我一看1e5就觉得得用快速幂来着

#include <bits/stdc++.h>
using namespace std;

const int N=2;

void multi(vector<vector<long long>> &a,vector<vector<long long>> b,long long mod){
    vector<vector<long long>> tmp(2,vector<long long>(2,0));
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            for(int k=0;k<N;k++){
                tmp[i][j]+=a[i][k]*b[k][j];
                tmp[i][j] = (tmp[i][j]%mod+mod)%mod;
            }
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            a[i][j]=tmp[i][j];
}
 

void Pow(vector<vector<long long>> &a,int n,long long mod){
    vector<vector<long long>> res(2,vector<long long>(2,0));
    for(int i=0;i<N;i++) res[i][i]=1;
    while(n){
        if(n&1)multi(res,a,mod);
        multi(a,a,mod);
        n>>=1;
    }
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            a[i][j]=res[i][j];
}



int main(){
    int T;
    long long mod = 1e9+7;
    cin>>T;
    while(T--){
        long long A,B,n;
        cin>>A>>B>>n;
        vector<vector<long long>> a = {{A*A-B,-A*B},{A,-B}};
        
        for(int i = 0;i<2;i++)for(int j = 0;j<2;j++)
            a[i][j] = (a[i][j]%mod+mod)%mod;
        
        if(n==1){
            cout<<A<<endl;
            continue;
        }
        if(n==2){
            long long ans = (A*A-2*B);
            ans = (ans%mod+mod)%mod;
            cout<<ans<<endl;
            continue;            
        }
        long long f0 = 2;
        long long f1 = A;
        long long f2 = (A*A-2*B%mod+mod)%mod;
        
        if(n%2==0){
            int cnt = n/2-1;
            Pow(a,cnt,mod);
            long long fn = ((a[0][0]*f2)%mod+(a[0][1]*f1)%mod+mod)%mod;
            cout<<fn<<endl;
        }
        else{
            int cnt = n/2;
            Pow(a,cnt,mod);
            long long fn = ((a[0][0]*f1)%mod+(a[0][1]*f0)%mod+mod)%mod;
            cout<<fn<<endl;
        }
    }
    return 0;
}

编辑于 2022-03-04 14:07:08 回复(0)

亲切的杰尼龟顶呱呱

容易出错的点：

1）用long long 类型数据做运算;

2）数据溢出和输入是负数的情形：
if(f[i] < 0) {
f[i] += modBase;
}

发表于 2021-10-27 19:33:56 回复(1)

牛客474721145号

思路：动态规划

转移方程：x^(n) + y^(n) = (x^(n-1) + y^(n-1))*(x+y) - x*y*(x^(n-2) + y^(n-2))，dp[n] = dp[n-1]*A + B*dp[n-2];

发表于 2021-08-09 12:06:25 回复(5)

社畜a

有没有大佬告诉我，下面的代码哪里错了

#include 
#include 
using namespace std;
const int MOD=1e9+7;
int dfs(int a,int b,int c){
    vector vec;
    vec.push_back(0);
    if(c==1) return a;
    if(c==2) return ((a*a)%MOD-(2*b)%MOD+MOD)%MOD;
    vec.push_back(a);
    vec.push_back(((a*a)%MOD-(2*b)%MOD+MOD)%MOD);
    for(int i = 3;i<=c;i++){
        vec.push_back(((a*vec[i-1])%MOD-(b*vec[i-2])%MOD+MOD) % MOD);
    }
    return vec.back();
}
int main() {
    int n;
    cin>>n;
    for(int i = 0;i<n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        cout<<dfs(a,b,c)<<endl;
    }
}

编辑于 2024-04-09 13:42:16 回复(0)

愉快的猕猴桃在泡池子

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*
光想着还是得利用下快速幂，然而不知道是在哪里溢出了还是咋滴，家人们谁懂呀。。。
(x+y)(x^n+y^n) = x^{n+1} + x^n * y + x * y^n + y^{n+1}
=>  x^{n+1} + y^{n+1} = (x^n+y^n) * (x+y) - (x^{n-1} + y^{n-1}) * xy

x^{2n}+y^{2n} = {x^n + y^n}^2 - 2*(xy)^n
*/
vector<long> xy_to_n(100003,-1);
vector<long> x_plus_y_to_n(100003,-1);
long mod = 1e9+7;

long calculate_xy_to_n(int n){
    if(xy_to_n[n]!=-1)
        return xy_to_n[n];
    long tmp = calculate_xy_to_n(n>>1);
    xy_to_n[n] = tmp*tmp;
    if(n&1) // 奇数
        xy_to_n[n]*=calculate_xy_to_n(1);
    if(xy_to_n[n]>=mod)
        xy_to_n[n] %= mod;
    if(xy_to_n[n]<0)
        xy_to_n[n] += mod;
    return xy_to_n[n];
}

long calculate_x_plus_y_to_n(int n){
    if(x_plus_y_to_n[n]!=-1)
        return x_plus_y_to_n[n];
    if(n&1){ // 奇数
        x_plus_y_to_n[n] = calculate_x_plus_y_to_n(n-1)*calculate_x_plus_y_to_n(1)
                           -calculate_x_plus_y_to_n(n-2)*calculate_xy_to_n(1);
    }else{ //偶数
        x_plus_y_to_n[n] = calculate_x_plus_y_to_n(n>>1)*calculate_x_plus_y_to_n(n>>1)
                           -2*calculate_xy_to_n(n>>1);
    }
    if(x_plus_y_to_n[n]>=mod)
        x_plus_y_to_n[n]%=mod;
    if(x_plus_y_to_n[n]<0)
        x_plus_y_to_n[n]+=mod;
    return x_plus_y_to_n[n];
}

int main() {
    int T;
    cin>>T;
    for(int i=0;i<T;i++){
        long xy,x_plus_y,n;
        cin>>x_plus_y>>xy>>n;
        xy_to_n.resize(n+1);
        std::fill(xy_to_n.begin(),xy_to_n.end(),-1);
        x_plus_y_to_n.resize(n+1);
        std::fill(x_plus_y_to_n.begin(),x_plus_y_to_n.end(),-1);
        xy_to_n[1]=xy;
        x_plus_y_to_n[1] = x_plus_y;
        cout<<calculate_x_plus_y_to_n(n)<<endl;
    }
}
// 64 位输出请用 printf("%lld")

发表于 2023-05-06 14:03:53 回复(0)

牛客219521847号

这道题不TLE的关键是自己写 power方程，每一步都mod一次。。。。

发表于 2021-10-18 12:38:04 回复(0)

onestan

#include <bits/stdc++.h>

using namespace std;

#define MOD (int)(1e9+7)

int f(int a,int b,int n)

{

vector<long long> func(3);

func[1]=2;

func[2]=a;

for(int i=2;i<=n;++i)

{

func[0]=func[1];

func[1]=func[2];

func[2]=(a*func[1]-b*func[0])%MOD;

if(func[2]<0)func[2]+=MOD;

}

return func[2];

}

int main()

{

int t,a,b,n;

cin>>t;

for(int i=0;i<t;++i)

{

cin>>a>>b>>n;

cout<<f(a,b,n)<<endl;

}

return 0;

}

发表于 2021-08-26 16:21:30 回复(0)

乔木少年

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;

int helper(int A, int B, int n) {
    if(n == 0) {
        return 2;
    }
    if(n == 1) {
        return A;
    }
    vector<long long> dp(n + 1);
    dp[0] = 2;
    dp[1] = A;
    
    for(int i = 2; i <= n; ++i) {
        dp[i] = (((A * dp[i - 1] % mod) - (B * dp[i - 2] % mod)) + mod) % mod;
    }
    
    return dp[n];
}

int main() {
    int t;
    cin >> t;
    while(t--) {
        int A, B, n;
        cin >> A >> B >> n;
        cout << helper(A, B, n) << endl;
    }
    return 0;
}

发表于 2021-08-11 11:46:48 回复(0)

想要进大厂的牛牛

#include<iostream>
#include<cstdlib>
#include<math.h>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include "string"
#include <hash_map>
#include <map>
#include <unordered_map>
#include <stack>
#include <stdio.h>
#include <queue>
#include <functional>
#include <set>
using namespace std;
const int mod = 1e9+7;
long long int XNYN(long long int A,long long int B,long long int n)
{
   if (n == 0)
   {
       return 2;
   }
   if (n == 1)
   {
       return A;
   }
   vector<long long int> dp(n+1,0);
   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];
}
int main()
{
   int cyc;
   cin>>cyc;
   vector<vector<int>> num;
   while (cyc > 0)
   {
       vector<int> tempNum;
       long long int A;
       long long int B;
       int n;
       cin >> A;
       cin >> B;
       cin >> n;
       if (cin.get() == '\n')
       {
           tempNum.push_back(A);
           tempNum.push_back(B);
           tempNum.push_back(n);
       }
       num.push_back(tempNum);
       cyc--;
   }
   for (int i = 0 ; i < num.size(); i++)
   {
       cout<<XNYN(num[i][0],num[i][1],num[i][2])<<endl;
   }
   system("pause");
   return 0;
}

发表于 2021-08-03 14:49:55 回复(0)

牛客622467775号

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
class Solution{
public:
    static const int mod = 1e9 + 7;
    vector<LL>res;
    LL a, b, n;
    LL ans0, ans1, ans;
    vector<LL> calculate(vector<vector<LL>>& nums, int len) {
        for (int i = 0; i < len; i++) {
            a = nums[i][0];
            b = nums[i][1];
            n = nums[i][2];
            vector<LL>temp;
            ans0 = a % mod;
            ans1 = (a * a % mod - 2 * b % mod + mod) % mod;
            if (n == 1) {
                res.push_back(ans0);
            }
            if (n == 2) {
                res.push_back(ans1);
            }
            else {
                temp.push_back(ans0);
                temp.push_back(ans1);
                ///ans = a * ans1 - b * ans0;
                ///temp.push_back(ans);
                for (int j = 2; j < n; j++) {
                    LL now = (a * temp[j - 1] % mod - b * temp[j - 2] % mod + mod) % mod;
                    temp.push_back(now);
                }
                LL size = temp.size();
                ans = temp[size - 1];
                res.push_back(ans);
            }
        }
        return res;
    }
     
    //int backtracking(int a, int b, int n, int ans, int ans0, int ans1, int startIndex) {
    //  if (startIndex == n) { return ans; }
    //  else {
    //      ans0 = ans1;
    //      ans1 = ans;
    //      ans = ans = a * ans1 - b * ans0;
    //      backtracking(a, b, n, ans, ans0, ans1, startIndex + 1);
    //  }
    //}
};
 
 
 
int main() {
    LL n;
    LL b;
    LL t;
    vector<vector<LL>>input;
    vector<LL>output;
    cin >> n;
    t = n;
    while (--n >= 0) {
        vector<LL>temp;
        for (int i = 0; i < 3; i++) {
            cin >> b;
            temp.push_back(b);
        }
        input.push_back(temp);
    }
    Solution result;
    output = result.calculate(input, t);
    for (int j = 0; j < t; j++) {
        cout << output[j] << endl;
    }
}

发表于 2021-07-30 11:26:46 回复(0)

Python

OPPO内推码_80378832_必过

import math
T = int(input())
for i in range(T):
A, B, n = map(int, input().split())
delta = A**2 - 4*B
if delta >= 0:
x = (A + math.sqrt(delta))/2
ans = (x**n + (A-x)**n) % (10**9+7)
print(int(ans))
else:
ans = 999999993
ans = ans % (10**9+7)

print(ans)

为什么这样子不行？

发表于 2021-07-27 22:39:26 回复(0)

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)

牛客566012114号

import java.util.*;

public class Main{


    /**
     * 阿里2 已知 x+y=A xy = B 求x^n+y^n
     * 递推式 xn = Axn-1 - Bxn-2
     */

    static long mod = (long)Math.pow(10,9)+7;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        for(int i=0;i<m;i++){
            long a = in.nextInt();
            long b = in.nextInt();
            int n = in.nextInt();
            a %= mod;
            b %= mod;
            System.out.println(solve(a,b,n));
        }
    }

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

}

编辑于 2021-06-29 18:26:25 回复(1)

Dominic789654

我这样运行时间超了，大佬能帮忙看看吗 python解法

T = int(input())
mod_num = 10 ** 9 + 7
for _ in range(T):
    A, B, n = map(int, input().split())
    if n == 1:
        print(A)
    elif n == 2:
        print((A ** 2 - 2 * B) % mod_num)
    else:
        rn1, rn2 = (A ** 2 - 2 * B) % mod_num, A
        res = 0
        while n > 2:
            res = (A * rn1 - B * rn2)
            rn2 = rn1
            rn1 = res
            n -= 1
        print(res)

编辑于 2021-06-19 22:31:45 回复(8)