The 14th UESTC Programming Contest Final B - Banana Watch 預處理、字首和

B - Banana Watch

Time Limit: 1000/1000MS (Java/Others)     Memory Limit: 262144/262144KB (Java/Others)

Submit 

Status

As a famous technology company, Banana Inc. invents Banana Watch, redefining the watch.

While a normal watch has 12 indexes and two or three moving hands, a Banana Watch has n indexes

and a moving hand.

The moving hand is at 0 initially, and in 1st second,

it turns 1 index

clockwise; in 2nd second,

it turns 2 indexes

clockwise; ... ;

 in ith second, it turns 

i indexes clockwise. When it moves back to 0 exactly,

one minute passes (Yes, Banana Inc. also redefines the minute).

How many seconds in the first minute?

Input

One integer n.

3≤n≤106

Sample input and outputOutput

Print the number of seconds in the first minute.

Sample Input	Sample Output
3	2
5	4

Hint

If n=5, in 1st second,

the hand moves to 1;

in 2nd second,

the hand moves to 3;

in 3rd second,

in 4th second, 

the hand moves to 0. So the answer for n=5 is 4.

My Solution

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

然後考慮到資料範圍。是以第一發有maxn = 2000000 + 1000，然後就過了。

假設用 1000000 + 8可能過也可能過不了。

#include <iostream>
#include <cstdio>
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;
}      

Thank you!