結果

問題 No.3688 LCM Sum
コンテスト
ユーザー hiromi_ayase
提出日時 2026-09-13 12:45:50
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 1,194 ms / 3,000 ms
+ 329µs
コード長 1,317 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,803 ms
コンパイル使用メモリ 376,296 KB
実行使用メモリ 237,696 KB
最終ジャッジ日時 2026-09-13 12:46:08
合計ジャッジ時間 12,088 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

#include <atcoder/all>
using namespace std;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
#define FAST_IO                \
  ios::sync_with_stdio(false); \
  cin.tie(0);
const i64 INF = 1001001001001001001;
using Modint = atcoder::static_modint<998244353>;

int main() {
  FAST_IO

  int N, M;
  cin >> N >> M;
  if (N > M) swap(N, M);

  // sum(lcm(a, b), 1<=a<=N, 1<=b<=M)
  // = sum([g], g * sum([a,b], ab)) (1<=a<=N/g, 1<=b<=M/g, gcd(a,b)=1)
  // = sum([g], sum([d], g * mu(d) * d^2 * sum([a, b], ab)))  (1<=a<=N/gd, 1<=b<=M/gd)
  // = sum([i], sum([d], i * mu(d) * d * sum([a, b], ab)))  (1<=a<=N/i, 1<=b<=M/i)
  // = sum([i], i * ab * sum([d], mu(d) * d)))  (1<=a<=N/i, 1<=b<=M/i, d|i)


  vector<int> lp(N + 1, -1);
  vector<Modint> f(N + 1, 1);
  for (int i = 2; i <= N; i ++) {
    if (lp[i] < 0) {
      for (int j = i; j <= N; j += i) {
        lp[j] = i;
      }
    }
    f[i] = f[i / lp[i]] * (i / lp[i] % lp[i] == 0 ? 1 : 1 - lp[i]);
  }

  Modint ans = 0;
  auto inv2 = Modint(2).inv();
  for (int i = 1; i <= N; i ++) {
    int n = N / i;
    int m = M / i;
    Modint ps = Modint(1) * n * (n + 1) * inv2;
    Modint qs = Modint(1) * m * (m + 1) * inv2;

    ans += i * ps * qs * f[i];
  }
  cout << ans.val() << endl;

}
0