[蓝桥杯][历届试题]数字游戏

题目

题目链接

题解

有一定的数据量了，因此直接暴力每次加一会超时。

因为我们只要求栋报的数之和，所以我们只要求出栋每次报的数即可。 绿色部分呈等差数列，因此我们知道上一次栋报的数便可以快速求出这次要报的数（通过等差数列求和公式），只要再将得到的数对k取模即可，累加取模后的值。T代表进行T轮，也就是求栋报的前T个数之和，因此上面过程进行T次。

注意：开LL。

代码

#include
using namespace std;
typedef long long ll;

ll a = 1, dong = 1, sum = 0, n, k, T;

int main()
{
	cin>>n>>k>>T;
	while(T--) {
		sum += dong;
		dong = (dong + n*a + n*(n-1)/2 ) % k;
		a = a + n;
	}	
	printf("%lld\n", sum);
	return 0;
}