Submission #35024990

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define TIME 1e3 * clock() / CLOCKS_PER_SEC
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ull = unsigned long long;
inline ll read() {
  ll x = 0, sgn = 0;
  char s = getchar();
  while(!isdigit(s)) sgn |= s == '-', s = getchar();
  while(isdigit(s)) x = x * 10 + s - '0', s = getchar();
  return sgn ? -x : x;
}
inline void print(int x) {
  if(x < 0) return putchar('-'), print(-x);
  if(x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
bool Mbe;
constexpr int V = 1e6;
constexpr int mod = 998244353;
void add(int &x, int y) {x += y, x >= mod && (x -= mod);}
bool vis[V + 5];
int n, c[V + 5], f[V + 5], s, ans;
int cnt, pr[V + 5], mu[V + 5];
bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  cin >> n;
  for(int i = 1, a; i <= n; i++) add(s, a = read()), c[a]++;
  mu[1] = 1;
  for(int i = 2; i <= V; i++) {
    if(!vis[i]) pr[++cnt] = i, mu[i] = -1;
    for(int j = 1; j <= cnt && i * pr[j] <= V; j++) {
      vis[i * pr[j]] = 1;
      if(i % pr[j] == 0) break;
      mu[i * pr[j]] = -mu[i];
    }
  }
  for(int i = 1; i <= V; i++) if(mu[i])
    for(int j = i; j <= V; j += i)
      add(f[j], mu[i] > 0 ? i : mod - i);
  for(int T = 1; T <= V; T++) {
    int g = 0;
    for(int i = 1; i <= V / T; i++) add(g, 1ll * i * c[i * T] % mod);
    add(ans, 1ll * T * f[T] % mod * g % mod * g % mod);
  }
  cout << 1ll * (ans + mod - s) * (mod + 1 >> 1) % mod << "\n";
  cerr << TIME << " ms\n";
  return 0;
}
/*
2022/9/21
author: Alex_Wei
start coding at 11:24
finish debugging at 12:27
*/

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:55:40: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   55 |   cout << 1ll * (ans + mod - s) * (mod + 1 >> 1) % mod << "\n";
      |                                    ~~~~^~~

Judge Result