Submission #471556

#	Time	Username	Problem	Language	Result	Execution time	Memory
471556		rainboy	Sažetak (COCI17_sazetak)	C11	64 / 160	1095 ms	264 KiB

sazetak

#include <stdio.h>

#define N	10
#define INF	0x3f3f3f3f

int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

int lcm(int a, int b) {
	long long c = a / gcd(a, b) * b;

	return c > INF ? INF : c;
}

int solve(int n, int a, int b) {
	int x, ans;

	ans = 0;
	for (x = b; x < n; x += b)
		if (x % a == 1)
			ans++;
	return ans;
}

int main() {
	static int kk[1 << N], aa[1 << N];
	int n, a, i, b, b1, b2;
	long long ans;

	scanf("%d%d", &a, &n);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[1 << i]);
	ans = 0;
	aa[0] = 1;
	for (b = 1; b < 1 << n; b++) {
		aa[b] = lcm(aa[b & -b], aa[b & b - 1]);
		kk[b] = kk[b & b - 1] + 1;
	}
	ans = 0;
	for (b1 = 1; b1 < 1 << n; b1++)
		for (b2 = 1; b2 < 1 << n; b2++)
			if ((b1 & b2) == 0)
				ans += solve(a - 1, aa[b1], aa[b2]) * ((kk[b1] + kk[b2]) % 2 == 0 ? 1 : -1);
	for (i = 0; i < n; i++)
		if ((a - 1) % aa[1 << i] == 0) {
			ans++;
			break;
		}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

sazetak.c: In function 'main':
sazetak.c:37:36: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   37 |   aa[b] = lcm(aa[b & -b], aa[b & b - 1]);
      |                                  ~~^~~
sazetak.c:38:20: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   38 |   kk[b] = kk[b & b - 1] + 1;
      |                  ~~^~~
sazetak.c:31:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  scanf("%d%d", &a, &n);
      |  ^~~~~~~~~~~~~~~~~~~~~
sazetak.c:33:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   scanf("%d", &aa[1 << i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 64 / 160