oj.uz

답안 #471559

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
471559 2021-09-09T19:01:27 Z rainboy Sažetak (COCI17_sazetak) C
160 / 160
 4 ms 204 KB 
#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 = (long long) 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]);
	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, 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

sazetak.c: In function 'main':
sazetak.c:39:36: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   39 |   aa[b] = lcm(aa[b & -b], aa[b & b - 1]);
      |                                  ~~^~~
sazetak.c:40:20: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   40 |   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
160.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 4 ms 204 KB Output is correct
10 Correct 4 ms 204 KB Output is correct