蓝桥杯历届试题(2014) REV-23 数字游戏

问题描述

  栋栋正在和同学们玩一个数字游戏。
  游戏的规则是这样的:栋栋和同学们一共n个人围坐在一圈。栋栋首先说出数字1。接下来,坐在栋栋左手边的同学要说下一个数字2。再下面的一个同学要从上一个同学说的数字往下数两个数说出来,也就是说4。下一个同学要往下数三个数,说7。依次类推。
  为了使数字不至于太大,栋栋和同学们约定,当在心中数到 k-1 时,下一个数字从0开始数。例如,当k=13时,栋栋和同学们报出的前几个数依次为:
  1, 2, 4, 7, 11, 3, 9, 3, 11, 7。
  游戏进行了一会儿,栋栋想知道,到目前为止,他所有说出的数字的总和是多少。

输入格式

  输入的第一行包含三个整数 n,k,T,其中 n 和 k 的意义如上面所述,T 表示到目前为止栋栋一共说出的数字个数。

输出格式

  输出一行,包含一个整数,表示栋栋说出所有数的和。

样例输入

3 13 3

样例输出

17

样例说明

  栋栋说出的数依次为1, 7, 9,和为17。

数据规模和约定

  1 < n,k,T < 1,000,000;

资源限制

时间限制:1.0s   内存限制:256.0MB

 1 /*
 2 看到这道题,大家会觉得这个比较简单,用等差数列就行了,
 3 通项公式求起来也蛮简单,是a(n)=((n+1)*n/2+1)%k。 
 4 但是,这种想法是错误的,可以是可以这样做,但是这种做法
 5 不是全对的做法。
 6 全对的做法是“利用上次报数去求下一次报数”,以输入为3,13,3为例
 7 栋栋报数为1,7,9,在没有与k求余数之前的数值为1,7,22 
 8 可以这样对1,7,22这三个数分解
 9 1
10 1 +1+2+3   =7 
11 7 +4+5+6   =22
12 我们发现下一次报数的计算被拆分成两部分:
13 一部分是上一次报数pre
14 一部分是一个规律的数列之和
15 pre就不说了,说下有规律的数列的特点: 
16 ①这部分的数列是一个等差数列; 
17 ②上界=上一轮报数时的上界+n; 
18 ③下界=上一轮的报数时的下界+n; 
19 ④从第二轮报数出现; 
20 根据这些信息,我们可以得到栋栋报的数列q的递推式
21 q(i+1)= (q(i)+(low+high)*n/2)%k   0=<i<T,q(0)=1 
22 */
23 #include<iostream>
24 #include<cmath>
25 #define ull unsigned long long
26 using namespace std;
27 ull cal(ull pre,ull k,ull low,ull high,ull n){
28     return (pre+(low+high)*n/2)%k;
29 }
30 int main(){
31     ull n,k,T;
32     cin>>n>>k>>T;
33     ull sum=0;
34     ull pre=1;
35     ull low=1;
36     ull high=n;
37     for(ull i=0;i<T;i++){
38         sum+=pre;
39         pre=cal(pre,k,low,high,n);
40         low+=n;
41         high+=n;
42         
43     } 
44     //sum+=pre;
45     cout<<sum<<endl;
46     return 0;
47 } 

 

上一篇:[题解]UVA1603 破坏正方形 Square Destroyer


下一篇:Fear Factoring(分块)