zcmu-2096 數字遊戲（思維+數列）

2096: 數字遊戲

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 211  Solved: 61

[Submit][Status][Web Board]

Description

棟棟正在和同學們玩一個數字遊戲。

　　遊戲的規則是這樣的：棟棟和同學們一共n個人圍坐在一圈。棟棟首先說出數字1。接下來，坐在棟棟左手邊的同學要說下一個數字2。再下面的一個同學要從上一個同學說的數字往下數兩個數說出來，也就是說4。下一個同學要往下數三個數，說7。依次類推。

　　為了使數字不至于太大，棟棟和同學們約定，當在心中數到 k-1 時，下一個數字從0開始數。例如，當k=13時，棟棟和同學們報出的前幾個數依次為：

1, 2, 4, 7, 11, 3, 9, 3, 11, 7。

　　遊戲進行了一會兒，棟棟想知道，到目前為止，他所有說出的數字的總和是多少。

Input

輸入的第一行包含三個整數 n,k,T，其中 n 和 k 的意義如上面所述，T 表示到目前為止棟棟一共說出的數字個數。

Output

輸出一行，包含一個整數，表示棟棟說出所有數的和。

Sample Input

3 13 3

Sample Output

17

HINT

1 < n,k,T < 1,000,000；

Source

曆屆試題

【分析】 題不難，搞不拎清為啥這道題弄了這麼久。心情煩躁

1. 先模拟一下題上的例子（n=3,k=13,t=3）這個人報數一次是1、7、9、7。1---1+1+2+3---1+1+2+3+4+5+6 依次類推，每次步長即為上一次的和加上3個連續的數。
2. 由1，每次相當于從1 2 3 4 5 6 7 ...等差數列中取連續的n個數求和做步長。第i次取的首項first=n(i-1)+1，尾項為n(i-1)+n；那麼第i次的步長s=(first+first+n-1)*n/2；注意取模，不然會爆。

【代碼】

#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long n,k,t;
	while(~scanf("%lld%lld%lld",&n,&k,&t))
	{
		long long ans=1,now=1;
		for(int i=1;i<t;i++)
		{
			long long first=n*(i-1)+1;
			long long s=n*(first+first-1+n)/2%k;
			now=(now+s)%k;
			ans+=now;
		}
		printf("%lld\n",ans);
	}
	return 0;
}