結果

問題 No.1899 L1 Cafe
コンテスト
ユーザー 👑 ygussany
提出日時 2022-03-20 11:32:35
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 83 ms / 2,000 ms
コード長 822 bytes
コンパイル時間 330 ms
コンパイル使用メモリ 29,824 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-28 04:07:03
合計ジャッジ時間 2,537 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0