蓝桥-历届试题 数字游戏

题目描述
栋栋正在和同学们玩一个数字游戏。
游戏的规则是这样的：栋栋和同学们一共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；
GG,看到这道题我以为是道简单的模拟题，然后很快写完后发现时间复杂度去到了O（n2），堪比冒泡排序，所以觉得会TLE，不过鉴于之前几次蓝桥杯给的数据太弱以为可以水过一下结果还真的TLE了...(果然不能抱着侥幸的心理做题)。后面在纸上模拟了一下发现每次栋栋的数有规律，是一段的求和，然后脑子突然想到前不久刚学的树状数组求任意区间和，兴高采烈地以为运用上了结果自己调试的时候发现速度还是太慢，交上去运行错误。最后看了网上别人的思路才发现这是到规律题。
由两种思路，第一种是列出数据会发现当K为奇数的时候，数据成以K为周期循环；当K为偶数的时候，数据以K2伟周期循环，所以我们只有求K长度即可，后面的就是从K序列中取出数字相加即可（注意：此题数据都要有long long不然数据会超出int范围）

1.png
第二种方法就是用等差数列求和，我们会发现首step（步长）是以(n+1)n/2首项，step以n*n为差的等差递增序列，num则等于（num+step）mod k；
此外还有个方法就是每次栋栋数的数都是1,2,3...,i的等差序列和+1，例如（以样例为例子）：
1 = (0+1)mod 13, 7 = (1+2+3+1)mod 13, 9 = (1+2+3+4+5+6+1)mod 13,所以是以n为周期的递增序列也可用等差求和公式求出每个数相加。
先附上我一开始的树状数组解题的代码,就当温习树状数组知识了（RE）（运行错误）

#include <iostream>
#include <cstring>
#define MAXN1 100000+10
#define MAXN2 200000+10
using namespace std;
int b[MAXN1],s[MAXN2];

int lowbit(int x){
    return x&-x;
}

void add(int d,int x){
    while(x<=MAXN2){
        s[x]+=d;
        x+=lowbit(x);
    }
}

int sum(int x){
    int ans = 0;
    while(x>0){
        ans+=s[x];
        x-=lowbit(x);
    }
    return ans;
}

int ask(int l,int r){
    return sum(r)-sum(l);
}
int main()
{
    memset(s,0,sizeof(s));
    int n,k,t,y;
    long long  num = 1,x;
    cin>>n>>k>>t;
    for(int i=1;i<=MAXN1;i++){
        y = i%k;
        add(y,i);
    }
    for(int i = 1;i<=(t-1);i++){
        x = (sum(i*n)+1)%k;
        num+=x;
    }
    cout<<num;
    return 0;
}

第一种方法（找周期）的AC代码：

#include <iostream>
#include <iostream>
#include <cstring>
#define MAXN1 100000+10
#define MAXN2 200000+10
using namespace std;
typedef long long LL;

LL myfind[MAXN2];

int main()
{
    LL n,k,t,temp,num = 1,sum = 0;
    cin>>n>>k>>t;
    if(k%2==0){
        temp = k*2;
        for(LL i = 1;i<=temp;i++){
            myfind[i] = num;
            num+=i;
            num%=k;
            }
    }
    else{
        temp = k;
        for(LL i = 1;i<=temp;i++){
            myfind[i] = num;
            num+=i;
            num%=k;
        }
    }
    while(t--){
        LL x = (t*n+1)%temp;
        if(x==0)
            x=1;
        sum+=myfind[x];
    }
    cout<<sum;
    return 0;
}

第二种方法（step步长）的AC代码：

#include <iostream>
#include <cstring>

using namespace std;
typedef long long LL;
int main()
{
    LL n,k,t,step,num = 1,sum = 1;
    cin>>n>>k>>t;
    step = (n+1)*n/2;
    for(int i = 1;i<t;i++,step+=n*n){
         num+=step;
         num%=k;
         sum+=num;
    }
    cout<<sum;
    return 0;
}

第三种方法（WA 86分）（由于蓝桥官网现在不提供数据下载，我现在还没看懂哪里出错了，欢迎指出）

#include <iostream>
#include <cstring>

using namespace std;
typedef long long LL;
int main()
{
    LL n,k,t,x,num,sum = 1;
    cin>>n>>k>>t;
    x = n;
    for(LL i = 1;i<t;i++,x+=n){
        num = (x+1)*x/2+1;
        num%=k;
        sum+=num;
    }
    cout<<sum;
    return 0;
}