Submission #545924

#TimeUsernameProblemLanguageResultExecution timeMemory
545924rainboyToys (CEOI18_toy)C11
100 / 100
564 ms26372 KiB
#include <stdio.h>

#define N	10000000	/* guess */
#define K	1344

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int dd[K]; char prime[K];
long long aa[N]; int n;

void solve(int x, int h, int a) {
	if (h == -1) {
		aa[n++] = a;
		return;
	}
	if (x % dd[h] == 0)
		solve(x / dd[h], h, a + dd[h] - 1);
	if (!prime[h] || x % dd[h] != 0)
		solve(x, h - 1, a);
}

void sort(long long *aa, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r;
		long long a = aa[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (aa[j] == a)
				j++;
			else if (aa[j] < a) {
				tmp = aa[i], aa[i] = aa[j], aa[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = aa[j], aa[j] = aa[k], aa[k] = tmp;
			}
		sort(aa, l, i);
		l = k;
	}
}

int main() {
	int n_, x, a, k, h, i;

	scanf("%d", &x);
	k = 0;
	for (a = 2; a <= x / a; a++)
		if (x % a == 0) {
			dd[k++] = a;
			prime[k - 1] = 1;
			for (h = 0; h < k - 1; h++)
				if (dd[k - 1] % dd[h] == 0) {
					prime[k - 1] = 0;
					break;
				}
		}
	for (a--; a > 0; a--)
		if (x % a == 0 && a != x / a) {
			dd[k++] = x / a;
			prime[k - 1] = 1;
			for (h = 0; h < k - 1; h++)
				if (dd[k - 1] % dd[h] == 0) {
					prime[k - 1] = 0;
					break;
				}
		}
	solve(x, k - 1, 0);
	sort(aa, 0, n);
	n_ = 0;
	for (i = 0; i < n; i++)
		if (n_ == 0 || aa[n_ - 1] != aa[i])
			aa[n_++] = aa[i];
	n = n_;
	printf("%d\n", n);
	for (i = 0; i < n; i++)
		printf("%lld ", aa[i]);
	printf("\n");
	return 0;
}

Compilation message (stderr)

toy.c: In function 'main':
toy.c:49:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |  scanf("%d", &x);
      |  ^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...