The 14th UESTC Programming Contest Final B – Banana Watch 预处理、前缀和

My Solution

用sum[i]表示1~i的和，然后，从1 ~ maxn 查找，第一次出现if((sum[i] %= n) == 0) {printf("%d", i); break;}

然后考虑到数据范围，所以第一发有maxn = 2000000 + 1000，然后就过了。如果用 1000000 + 8可能过也可能过不了。

#include 
#include 
using namespace std;
const int maxn = 2000000 + 1000;
long long sum[maxn];
int main()
{
    int n;
    scanf("%d", &n);
    sum[0] = 0;
    for(int i = 1; i < maxn; i++){
        sum[i] += sum[i-1]+i;
        if((sum[i] %= n) == 0) {printf("%d", i); break;}
    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx