Submission #471557

#	Time	Username	Problem	Language	Result	Execution time	Memory
471557		rainboy	Sažetak (COCI17_sazetak)	C11	64 / 160	11 ms	280 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 inv(int a, int b) {
	return b == 1 ? 0 : (b - ((long long) inv(b, a % b) * b - 1) / (a % b)) % b;
}

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

	if (gcd(a, b) != 1)
		return 0;
	x = inv(a, b);
	return x > (n - 1) / a ? 0 : ((n - 1) / a - x) / b + 1;
}

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:40:36: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   40 |   aa[b] = lcm(aa[b & -b], aa[b & b - 1]);
      |                                  ~~^~~
sazetak.c:41:20: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   41 |   kk[b] = kk[b & b - 1] + 1;
      |                  ~~^~~
sazetak.c:34:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  scanf("%d%d", &a, &n);
      |  ^~~~~~~~~~~~~~~~~~~~~
sazetak.c:36:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |   scanf("%d", &aa[1 << i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 64 / 160