#747224 (C) No.1899 L1 Cafe

• 問題: No.1899 L1 Cafe
• ユーザー: ygussany
• 提出日時: 2022-03-20 11:32:35
• 言語: C (gcc 12.3.0)
• 結果: AC
• 実行時間: 84 ms / 2,000 ms
• コード長: 822 bytes
• コンパイル時間: 241 ms
• コンパイル使用メモリ: 29,824 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-05-06 02:03:27
• 合計ジャッジ時間: 2,275 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	62 ms; 5,376 KB
testcase_02	AC	67 ms; 5,376 KB
testcase_03	AC	30 ms; 5,376 KB
testcase_04	AC	39 ms; 5,376 KB
testcase_05	AC	19 ms; 5,376 KB
testcase_06	AC	84 ms; 5,376 KB
testcase_07	AC	47 ms; 5,376 KB
testcase_08	AC	51 ms; 5,376 KB
testcase_09	AC	50 ms; 5,376 KB
testcase_10	AC	59 ms; 5,376 KB
testcase_11	AC	54 ms; 5,376 KB
testcase_12	AC	62 ms; 5,376 KB

ソースコード

#include <stdio.h>

long long floor_sum(long long n, long long m, long long a, long long b)
{
	if (a >= m || b >= m) return n * (n - 1) * (a / m) / 2 + n * (b / m) + floor_sum(n, m, a % m, b % m);
	long long y = (n * a + b) / m, x = m * y - b;
	if (y == 0) return 0;
	else return (n - (x + a - 1) / a) * y + floor_sum(y, a, m, (a - x % a) % a);
}

long long solve(int N, int A, int B)
{
	int a = N + 1 - N / A * A, b = N + 1 - N / B * B;
	return (long long)(N + 1 + a) * ((N + 1 - a) / A + 1) / 2 + (long long)(N + 1 + b) * ((N + 1 - b) / B + 1) / 2 - floor_sum((N + 1 - a) / A + 1, B, A, a - 1) - ((N + 1 - a) / A + 1) - (N + 1) * 2 + 1;
}

int main()
{
	int t, T, N, A, B;
	scanf("%d", &T);
	for (t = 1; t <= T; t++) {
		scanf("%d %d %d", &N, &A, &B);
		printf("%lld\n", solve(N, A, B));
	}
	fflush(stdout);
	return 0;
}