Submission #7643710

---

Source Code Expand

#ifdef DBG1
  #define LOCAL
#endif

#ifdef LOCAL
  #define _GLIBCXX_DEBUG
#endif

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

#ifdef DBG1
    #define dbg(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dbg(...)
#endif

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;

const int P = 998244353;

int diff(int a, int b) {
  if ((a -= b) < 0) {
    a += P;
  }
  return a;
}

int sum(int a, int b) {
  if ((a += b) >= P) {
    a -= P;
  }
  return a;
}

int &add(int &a, int b) {
  return a = sum(a, b);
}

int &subtract(int &a, int b) {
  return a = diff(a, b);
}

int prod(int a, int b) {
  return int(ll(a) * b % P);
}

int power(int a, int n) {
  int b = 1;
  while (n) {
    if (n & 1) {
      b = prod(a, b);
    }
    a = prod(a, a);
    n /= 2;
  }
  return b;
}

int inverse(int a) {
  return power(a, P - 2);
}

void update(int &ans, vector<int> &sum, const vector<int> &factor, int a, int d) {
  add(ans, prod(a, prod(sum[d], factor[d])));
  add(sum[d], a);
}

bool solve() {
  int n;
  if (scanf("%d", &n) != 1) { return false; }
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }

  const int MAX = *max_element(a.begin(), a.end());

  vector<int> prime_div(MAX + 1);
  for (int i = 2; i <= MAX; ++i) {
    if (prime_div[i] == 0) {
      for (int j = i; j <= MAX; j += i) {
        prime_div[j] = i;
      }
    }
  }

  vector<int> factor(MAX + 1);
  for (int i = 1; i <= MAX; ++i) {
    factor[i] = inverse(i);
  }
  /*for (int i = 1; i <= MAX; ++i) {
    for (int d = 1; d * d <= i; ++d) {
      if (i % d == 0) {
        if (d != i) {
          subtract(factor[i], factor[d]);
        }
        int d2 = i / d;
        if (d2 != d && d2 != i) {
          subtract(factor[i], factor[d2]);
        }
      }
    }
    if (MAX <= 10) {
      dbg("factor[%d] = %d\n", i, factor[i]);
    }
  }*/
  //for (int i = 1; i <= MAX; ++i) {
  for (int i = MAX; i >= 1; --i) {
    vector<int> primes;
    for (int x = i; x > 1; ) {
      int p = prime_div[x];
      primes.push_back(p);
//        subtract(factor[i], prod(1, factor[i / p]));
      assert(x % p == 0 && p > 1);
      while (x % p == 0) {
        x /= p;
      }
    }

    int k = int(primes.size());
    for (int mask = 1; mask < (1 << k); ++mask) {
      int pr = 1, sign = 1;
      for (int j = 0; j < k; ++j) {
        if (mask & (1 << j)) {
          pr *= primes[j];
          sign = P - sign;
        }
      }
      //dbg("factor[%d] += %d * factor[%d]\n", i, sign, i / pr);
      add(factor[i], prod(sign, factor[i / pr]));
    }

    if (MAX <= 10) {
      dbg("factor[%d] = %d\n", i, factor[i]);
    }
  }

  if (MAX <= 100) {
  int total = 0;
  for (int i = 1; i <= MAX; ++i) {
    int sum = 0;
    for (int d = 1; d <= i; ++d) {
      if (i % d == 0) {
        total++;
        add(sum, factor[d]);
      }
    }
    //dbg("%d: %d != %d\n", i, sum, inverse(i));
    assert(sum == inverse(i));
  }
  dbg("total %d\n", total);
  }

  int ans = 0;
  vector<int> sum(MAX + 1);
  for (int i = 0; i < n; ++i) {
    for (int d = 1; d * d <= a[i]; ++d) {
      if (a[i] % d == 0) {

        update(ans, sum, factor, a[i], d);
        int d2 = a[i] / d;
        if (d2 != d) {
          update(ans, sum, factor, a[i], d2);
        }
      }
    }
  }
  printf("%d\n", ans);

  return true;
}

int main() {
  int tt = -1;
  //scanf("%d", &tt);
  while (tt-- && solve());
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘bool solve()’:
./Main.cpp:86:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &a[i]);
                       ^

Judge Result