結果
問題 | 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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 12 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /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; } }