【算法】小强爱数学(迭代公式+数论取模)

文章目录

    • 1. 问题
    • 2. 输入
    • 3. 输出
    • 4. 示例
    • 5. 分析
    • 6. 思路
    • 7. 数论,取模相关公式
    • 8. 数论,同余定理
    • 9. 代码

1. 问题

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

2. 输入

第一行输入一个正整数T.表示有T组数据
接下来T行, 每行输入三个整数A,B和n
1 < = T < = 100 0 < = A , B < = 1 e 9 + 7 1 < = n < = 1 e 5 1<=T<=100\\ 0<=A,B<=1e9+7\\ 1<=n<=1e5 1<=T<=1000<=A,B<=1e9+71<=n<=1e5

3. 输出

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

4. 示例

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

5. 分析

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

递推公式

在这里插入图片描述

证明
在这里插入图片描述

6. 思路

迭代计算,类似斐波那契。不过需要小心溢出问题。本题中,A、B的值可能不会很大,但A、B计算处理后得到的值溢出的概率极高。如果A、B均为int,那么计算时就极容易发生溢出现象,因此A、B类型设置为long

此外,最终结果需要取模,笔者额外介绍一下数论中有关取模的信息

7. 数论,取模相关公式

(a + b) % p = (a%p + b%p) %p
(a - b) % p = ((a%p - b%p) + p) %p
(a * b) % p = (a%p)*(b%p) %p

详细介绍的文章

  • 快速幂取模
  • 快速乘法取模

快速求模,其实就是运用到了取模的性质,把大的数字分部拆解为小的数字。当然拆的过程中会出现各种细节

一句话总结:拆出来的数字,都取模。切记除法、指数不要这么做


8. 数论,同余定理

如果(a - b)能够被m整除,即m | (a - b),那么a mod m = b mod m。我们称称整数a与b对模m同余,记作a≡b(mod m)

这个也好理解,a - b能够被m整除,说明a,和b mod m能够得到相同余数,只有这样,a - b才能把多余的数字去除,因此a - b才能被m整除

详细介绍的文章

  • 同余定理

9. 代码

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]);}}}
}

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/284812.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

数据结构(五)——树森林

5.4 树和森林 5.4.1 树的存储结构 树的存储1&#xff1a;双亲表示法 用数组顺序存储各结点&#xff0c;每个结点中保存数据元素、指向双亲结点(父结点)的“指针” #define MAX_TREE_SIZE 100// 树的结点 typedef struct{ElemType data;int parent; }PTNode;// 树的类型 type…

【Mysql】硬盘性能压测(Sysbench工具)

1、IOPS和吞吐量介绍 IOPS&#xff08;每秒输入/输出操作数&#xff09;&#xff1a;是衡量存储设备每秒能够执行的输入/输出操作的数量。对于数据库等需要频繁读写的应用程序而言&#xff0c;IOPS 是一个关键的性能指标。更高的 IOPS 意味着存储设备能够处理更多的读写请求&am…

【Vue】三、使用ElementUI实现图片上传

目录 一、前端代码实现 二、后端代码实现 三、调试效果实现 一、前端代码实现 废话不多说直接上代码 <el-form-item prop"image" label"上传图片" v-model"form.image"><el-upload:action"http://localhost:8…

基于springboot+vue的智慧生活商城系统

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、阿里云专家博主、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战&#xff0c;欢迎高校老师\讲师\同行交流合作 ​主要内容&#xff1a;毕业设计(Javaweb项目|小程序|Pyt…

Stable Diffusion 本地训练端口与云端训练端口冲突解决办法

方法之一&#xff0c;修改本地训练所用的端口 1 首先&#xff0c;进入脚本训练器的根目录 例如&#xff1a;C:\MarkDeng\lora-scripts-v1.7.3 找到gui.py 2 修改端口号 因为云端训练器也是占用28000和6006端口 那么本地改成27999和6007也是可以的 保存退出&#xff0c;运行启动…

如何在C语言中使用命令行参数

C语言文章更新目录 C语言学习资源汇总&#xff0c;史上最全面总结&#xff0c;没有之一 C/C学习资源&#xff08;百度云盘链接&#xff09; 计算机二级资料&#xff08;过级专用&#xff09; C语言学习路线&#xff08;从入门到实战&#xff09; 编写C语言程序的7个步骤和编程…

【C++】关联式容器——map和set

1 关联式容器 STL中我们常用的部分容器&#xff0c;比如&#xff1a;vector、list、deque、forward_list(C11)等&#xff0c;这些容器统称为序列式容器&#xff0c;因为其底层为线性序列的数据结构&#xff0c;里面存储的是元素本身。 那什么是关联式容器呢&#xff1f;它与序…

阿里云服务器2核4G服务器收费价格表,1个月和一年报价

阿里云2核4G服务器多少钱一年&#xff1f;2核4G服务器1个月费用多少&#xff1f;2核4G服务器30元3个月、85元一年&#xff0c;轻量应用服务器2核4G4M带宽165元一年&#xff0c;企业用户2核4G5M带宽199元一年。本文阿里云服务器网整理的2核4G参加活动的主机是ECS经济型e实例和u1…

JAVA面向对象编程 JAVA语言入门基础

类与对象的概念 类 (Class) 和对象 (Object) 是面向对象程序设计方法中最核心的概念。 类是对某一类事物的描述(共性)&#xff0c;是抽象的、概念上的定义&#xff1b;而对象则是实际存在的属该类事物的具体的个体&#xff08;个性&#xff09;&#xff0c;因而也称为实例(In…

透视未来工厂:山海鲸可视化打造数字孪生新篇章

在信息化浪潮的推动下&#xff0c;数字孪生工厂项目正成为工业制造领域的新宠。作为一名山海鲸可视化的资深用户&#xff0c;我深感其强大的数据可视化能力和数字孪生技术在工厂管理中的应用价值&#xff0c;同时我们公司之前也和山海鲸可视化合作制作了一个智慧工厂项目&#…

学习或复习电路的game推荐:nandgame(NAND与非门游戏)、Turing_Complete(图灵完备)

https://www.nandgame.com/ 免费 https://store.steampowered.com/app/1444480/Turing_Complete/ 收费&#xff0c;70元。据说可以导出 Verilog &#xff01;

转座子插入位点分析4------PS转座子测序数据分析

观察数据 这是经公司使用fastp质控后的数据&#xff0c;我们先挑选部分数据进行比对&#xff0c;观察序列结构 为了准确性&#xff0c;我们再次挑选另一批数据进行比对 可以看到&#xff0c;所有序列都存在一个“GTGTCAAATACTTATTTTCCCCGCTGTA”的前导序列&#xff0c;这可能…

深度学习pytorch——多层感知机反向传播(持续更新)

在讲解多层感知机反向传播之前&#xff0c;先来回顾一下多输出感知机的问题&#xff0c;下图是一个多输出感知机模型&#xff1a; 课时44 反向传播算法-1_哔哩哔哩_bilibili 根据上一次的分析深度学习pytorch——感知机&#xff08;Perceptron&#xff09;&#xff08;持续更新…

突破边界:Web3开启数字化社会的新纪元

引言 随着科技的不断进步和数字化社会的发展&#xff0c;Web3正逐渐成为了人们关注的焦点。作为新一代互联网的演进形态&#xff0c;Web3具有突破传统边界、实现去中心化的特点&#xff0c;被认为将开启数字化社会的新纪元。本文将深入探讨Web3的概念、特点、应用场景&#xf…

Java 自定义线程池实现

自定义线程池 简介任务图示阻塞队列 BlockingQueue<T>ReentrantLock代码 线程池 ThreadPool工作线程类 Worker 拒绝策略接口代码测试类 TestThreadPool为什么需要j i&#xff1f;&#xff08;lambad表达式相关&#xff09; 测试结果拒绝策略&#xff1a;让调用者自己执行…

外包干了6天,技术明显进步。。。

我是一名大专生&#xff0c;自19年通过校招进入湖南某软件公司以来&#xff0c;便扎根于功能测试岗位&#xff0c;一晃便是近四年的光阴。今年8月&#xff0c;我如梦初醒&#xff0c;意识到长时间待在舒适的环境中&#xff0c;已让我变得不思进取&#xff0c;技术停滞不前。更令…

mysql80-DBA数据库学习1

掌握能力 核心技能 核心技能 mysql部署 官网地址www.mysql.com 或者www.oracle.com https://dev.mysql.com/downloads/repo/yum/ Install the RPM you downloaded for your system, for example: yum install mysql80-community-release-{platform}-{version-number}.noarch…

Qt 写一个邮件发送程序

最近在完成一个邮箱代替的告警功能&#xff0c;写了一个邮件发送的demo 以下为代码&#xff1a; #ifndef MAINWINDOW_H #define MAINWINDOW_H#include <QMainWindow> #include<QTcpSocket> namespace Ui { class MainWindow; }class MainWindow : public QMainWin…

【STL源码剖析】【2、空间配置器——allocator】

文章目录 1、什么是空间配置器&#xff1f;1.1设计一个简单的空间配置器&#xff0c;JJ::allocator 2、具备次配置力( sub-allocation)的 SGI 空间配置器2.1 什么是次配置力2.2 SGI标准的空间配置器&#xff0c;std::allocator2.2 SGI特殊的空间配置器&#xff0c;std::alloc2.…

Java代码基础算法练习-公式求和-2024.03.24

任务描述&#xff1a; 求公式Snaaaaaa…aa…aaa&#xff08;有n个a&#xff09;之值&#xff0c;其中a是一个数字&#xff0c;为2。 例如&#xff0c;n5 时222222222222222&#xff0c;n 由键盘输入(n<5)。 任务要求&#xff1a; package march0317_0331;import java.util.…