結果

問題 No.2362 Inversion Number of Mod of Linear
コンテスト
ユーザー 👑 ygussany
提出日時 2023-06-22 01:49:35
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 170 ms / 2,000 ms
コード長 1,434 bytes
コンパイル時間 912 ms
コンパイル使用メモリ 31,488 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-29 10:29:15
合計ジャッジ時間 2,129 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <stdio.h>

__int128 generalized_floor_sum(long long n, long long m, long long a, long long b, __int128 p, __int128 q, __int128 r)
{
	if (n == 0) return 0;
	if (b >= m) return generalized_floor_sum(n, m, a, b % m, p, q, r + q * (b / m)) + p * (b / m) * n * (n - 1) / 2 + q * (b / m) * (b / m + 1) / 2 * n + r * (b / m) * n;
	if (a == 0) return 0;
	if (a >= m) return generalized_floor_sum(n, m, a % m, b, p + q * (a / m), q, r) + p * (a / m) * n * (n - 1) * (n * 2 - 1) / 6 + q * (a / m) * ((__int128)(a / m) * n * (n - 1) * (n * 2 - 1) / 6 + n * (n - 1) / 2) / 2 + r * (a / m) * n * (n - 1) / 2;
	
	long long y = (a * (n - 1) + b) / m;
	if (y == 0) return 0;
	return generalized_floor_sum(y, a, m, a * n - m * y + b, -q, -p, p * n + q * y + r);
}

__int128 generalized_floor_sum_naive(int n, int m, int a, int b, int p, int q, int r)
{
	int k, l;
	__int128 ans = 0;
	for (k = 0; k < n; k++) for (l = 1; l <= (a * k + b) / m; l++) ans += (long long)p * k + (long long)q * l + r;
	return ans;
}

long long solve(int N, int M, int X, int Y)
{
	return generalized_floor_sum(N, M, X, Y, 1, 0, 0) * 2 - generalized_floor_sum(N, M, X, Y, 0, 0, 1) * (N - 1) - generalized_floor_sum(N, M, X, 0, 0, 0, 1) * N + generalized_floor_sum(N, M, X, 0, 1, 0, 0);
}

int main()
{
	int T, N, M, X, Y;
	scanf("%d", &T);
	while (T--) {
		scanf("%d %d %d %d", &N, &M, &X, &Y);
		printf("%lld\n", solve(N, M, X, Y));
	}
	fflush(stdout);
	return 0;
}
0