HDU 1005 Number Sequence(数列)
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/32768 K (Java/Others)
【Description】 |
【题目描述】 |
A number sequence is defined as follows: f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7. Given A, B, and n, you are to calculate the value of f(n). |
一个数列定义如下: f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7。 给定A,B和n,要求计算f(n)的值。 |
【Input】 |
【输入】 |
The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed. |
多组输入。每个测试用例有一行3整数A,B和n(1 <= A, B <= 1000, 1 <= n <= 100,000,000)。最后一行为三个0,并且不被处理。 |
【Output】 |
【输出】 |
For each test case, print the value of f(n) on a single line. |
对于每个测试样例,输出f(n)的值在单独一行。 |
【Sample Input - 输入样例】 |
【Sample Output - 输出样例】 |
1 1 3 1 2 10 0 0 0 |
2 5 |
【题解】
一般这种mod X的问题都与找循环节有关。
当 a = b = 7的时候,后面的数都是0,所以用前两个数1 1最为循环的开头很不明智。
因此我们直接从第三个数开始计算并找循环节。
【代码 C++】
#include<cstdio>
int main(){
int i, a, b, n, data[];
while (scanf("%d%d%d", &a, &b, &n)){
if (a + b + n == ) break;
a %= ; b %= ; n -= ;
if (n < ){ puts(""); continue; }
data[] = (a + b) % ; data[] = (a*data[] + b) % ;
for (i = ; i <= n; ++i){
data[i] = (a*data[i - ] + b*data[i - ]) % ;
if (data[i] == data[] && data[i - ] == data[]){
--i;
break;
}
}
printf("%d\n", data[n%i]);
}
return ;
}
HDU 1005 Number Sequence(数列)的更多相关文章
-
HDU 1005 Number Sequence(数论)
HDU 1005 Number Sequence(数论) Problem Description: A number sequence is defined as follows:f(1) = 1, ...
-
HDU - 1005 Number Sequence 矩阵快速幂
HDU - 1005 Number Sequence Problem Description A number sequence is defined as follows:f(1) = 1, f(2 ...
-
HDU 1005 Number Sequence【斐波那契数列/循环节找规律/矩阵快速幂/求(A * f(n - 1) + B * f(n - 2)) mod 7】
Number Sequence Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)T ...
-
HDU 1005 Number Sequence【多解,暴力打表,鸽巢原理】
Number Sequence Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)T ...
-
HDU 1005 Number Sequence
Number Sequence Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)T ...
-
hdu 1005:Number Sequence(水题)
Number Sequence Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)T ...
-
HDU 1005 Number Sequence (模拟)
题目链接 Problem Description A number sequence is defined as follows: f(1) = 1, f(2) = 1, f(n) = (A * f( ...
-
HDU 1005 Number Sequence(矩阵)
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission( ...
-
HDU - 1005 Number Sequence (矩阵快速幂)
A number sequence is defined as follows: f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mo ...
随机推荐
-
AC日记——验证字串 openjudge 1.7 18
18:验证子串 总时间限制: 1000ms 内存限制: 65536kB 描述 输入两个字符串,验证其中一个串是否为另一个串的子串. 输入 输入两个字符串, 每个字符串占一行,长度不超过200且不 ...
-
Django的Context和RequestContext
参考:http://www.dannysite.com/blog/38/ Django的模板渲染中,Context可以用来传递数据,一个Context是一系列变量和值的集合,它和Python的字典有点 ...
-
HDU 5724 Chess (状态压缩sg函数博弈) 2016杭电多校联合第一场
题目:传送门. 题意:有n行,每行最多20个棋子,对于一个棋子来说,如果他右面没有棋子,可以移动到他右面:如果有棋子,就跳过这些棋子移动到后面的空格,不能移动的人输. 题解:状态压缩博弈,对于一行2^ ...
-
使用DriverManager获取数据库连接的一个小改进
由于使用DriverManager获取数据库连接时,由于DriverManager实现类中有一段静态代码块,可以直接注册驱动,且可以同时管理多个驱动程序 所以当换数据库连接时需要指定不同的数据库,那么 ...
-
python3--(变量)
变量: Python 是动态类型语言, 也就是说不需要预先声明变量的类型.变量是对象的引用,变量只是将指针指向了对象所在的内存地址.变量的类型和值在赋值那一刻被初始化. 变量起名: 1.显式--> ...
-
【2017-04-24】winform基础、登录窗口、窗口属性
一.winform基础 客户端应用程序:C/S 客户端应用程序可以操作用户电脑中的文件,代码要在用户电脑上执行,吃用户电脑配置. 窗体是由控件和属性做出来的 控件:窗体里所放的东西."视图 ...
-
TCP/IP学习
1.TCP/IP网络包括两部分 ①传输协议 ②网络协议
-
蓝牙SDP协议概述
之前写了一篇 bluedroid对于sdp的实现的源码分析 ,他其实对于sdp 协议本身的分析并不多,而是侧重于 sdp 处于Android bluedroid 架构中的代码流程,这篇文章,是针对 ...
-
UploadFtp
#!/bin/bash FILENAME=$ DSTDIR=$ FTPSRV=ip FTPUSER="user" FTPPWD="password" SRCDI ...
-
Django数据库数据表操作
建立表单 django通过设置类来快速建表,打开models.py 例: from __future__ import unicode_literals from django.db import m ...