結果
問題 | No.1899 L1 Cafe |
ユーザー | kakel-san |
提出日時 | 2023-11-23 22:52:52 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 208 ms / 2,000 ms |
コード長 | 2,066 bytes |
コンパイル時間 | 7,682 ms |
コンパイル使用メモリ | 166,604 KB |
実行使用メモリ | 216,396 KB |
最終ジャッジ日時 | 2024-09-26 08:22:27 |
合計ジャッジ時間 | 12,021 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 54 ms
30,464 KB |
testcase_01 | AC | 190 ms
62,208 KB |
testcase_02 | AC | 191 ms
66,816 KB |
testcase_03 | AC | 127 ms
51,200 KB |
testcase_04 | AC | 142 ms
56,320 KB |
testcase_05 | AC | 106 ms
43,520 KB |
testcase_06 | AC | 208 ms
66,808 KB |
testcase_07 | AC | 167 ms
57,984 KB |
testcase_08 | AC | 174 ms
58,616 KB |
testcase_09 | AC | 163 ms
57,600 KB |
testcase_10 | AC | 183 ms
60,928 KB |
testcase_11 | AC | 188 ms
67,264 KB |
testcase_12 | AC | 195 ms
216,396 KB |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (89 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System; using static System.Console; using System.Linq; using System.Collections.Generic; class Program { static int NN => int.Parse(ReadLine()); static int[] NList => ReadLine().Split().Select(int.Parse).ToArray(); public static void Main() { Solve(); } static void Solve() { var t = NN; var ans = new long[t]; for (var u = 0; u < t; ++u) { var c = NList; var (n, a, b) = (c[0], c[1], c[2]); var al = FloorSum(n / a + 1, 1, -a, n) - n; var bl = FloorSum(n + 1, b, -1, n) - n / b; var abl = FloorSum(n / a + 1, b, -a, n) - n / b; ans[u] = al + bl - abl; } WriteLine(string.Join("\n", ans)); } /// <summary> /// sum(x=[0..n); floor((ax + b)/m)) の値を求める<br /> /// 制約: 0<=n<=10^9, 1<=m<=10^9 /// </summary> static long FloorSum(long _n, long _m, long a, long b) { var (n, m) = ((ulong)_n, (ulong)_m); ulong ans = 0; if (a < 0) { var a2 = (ulong)((a % _m + _m) % _m); ans -= n * (n - 1) / 2 * ((a2 + (ulong)- a) / m); a = (long)a2; } if (b < 0) { var b2 = (ulong)((b % _m + _m) % _m); ans -= n * ((b2 + (ulong)- b) / m); b = (long)b2; } return (long)(ans + FloorSum(n, m, (ulong)a, (ulong)b)); } static ulong FloorSum(ulong n, ulong m, ulong a, ulong b) { ulong ans = 0; while (true) { if (a >= m) { ans += n * (n - 1) / 2 * (a / m); a %= m; } if (b >= m) { ans += n * (b / m); b %= m; } ulong yMax = a * n + b; if (yMax < m) break; n = yMax / m; b = yMax % m; (m, a) = (a, m); } return ans; } }