回复 29楼 吹水佬
我以后要认真读题,不过今次也学到了很多
回复 31楼 搬砖
21楼是正解,不超时用21楼~的解法~
#include <stdio.h> #define MAX 10000 int main() { int N = 8; size_t A[MAX] = {2, 5, 6, 3, 18, 7, 11, 19}; unsigned i, sum = 0, sa[MAX + 1] = {0}, ss[MAX][2] = {1}; // ss 记录sum第一次和第二次出现的位置 for (i = 0; i < N; ++i) { sum = (sum + A[i]) % N; sa[i + 1] = sum; if (ss[sum][1]) continue; ss[sum][ss[sum][0] != 0] = i + 2; } for (i = 0; i < N; ++i) { if (ss[sa[i]][1]) { printf("%u\n%u\n", ss[sa[i]][1] - ss[sa[i]][0], i + 1); break; } } return 0; }
#include <time.h> #include <stdio.h> #include <stdlib.h> #define MAX 10000 #define LEN sizeof(ttt) / sizeof(ttt[0]) unsigned ttt[] = { 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767}; void init(unsigned N, unsigned A[]) { unsigned i; srand((unsigned int) time(NULL)); for (i = 0; i < N; ++i) { A[i] = ttt[rand() % LEN] * ttt[rand() % LEN] + ttt[rand() % LEN]; } for (i = 0; i < N; ++i) { printf("%u%c", A[i], "\n "[i % 10 < 9]); } printf("\n\n"); } void display(unsigned sa[], unsigned ss[][2], unsigned N) { unsigned i, j; printf("r "); for (i = 0; i <= N; ++i) { printf("%4u%c", sa[i], "\n "[i < N]); } for (i = 0; i < 2; ++i) { printf("%d ", i + 1); for (j = 0; j <= N; ++j) { printf("%4u%c", ss[sa[j]][i], "\n "[j < N]); } } printf("\n"); } int main() { unsigned N = ttt[rand() % LEN], A[MAX]; unsigned i, sum = 0, sa[MAX + 1] = {0}, ss[MAX][2] = {1}; // ss 记录sum第一次和第二次出现的位置 init(N, A); for (i = 0; i < N; ++i) { sum = (sum + A[i]) % N; sa[i + 1] = sum; if (ss[sum][1]) continue; ss[sum][ss[sum][0] != 0] = i + 2; } display(sa, ss, N); for (i = 0; i < N; ++i) { if (ss[sa[i]][1]) { printf("%u\n%u\n", ss[sa[i]][1] - ss[sa[i]][0], i + 1); break; } } return 0; }