結果
| 問題 |
No.2940 Sigma Sigma Div Floor Problem
|
| コンテスト | |
| ユーザー |
 SnowBeenDiding
|
| 提出日時 | 2024-10-18 21:38:21 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,440 bytes |
| コンパイル時間 | 6,625 ms |
| コンパイル使用メモリ | 309,780 KB |
| 実行使用メモリ | 17,288 KB |
| 最終ジャッジ日時 | 2024-10-18 22:32:27 |
| 合計ジャッジ時間 | 33,224 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 WA * 1 |
| other | AC * 14 WA * 15 RE * 20 |
ソースコード
#include <atcoder/all>
#include <bits/stdc++.h>
#define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
using namespace atcoder;
using namespace std;
typedef long long ll;
template <class T, class S = T> struct AllPairOperationSum {
// https://shakayami.hatenablog.com/entry/2021/01/01/044946
// Σ op(a[i], a[j]) (i < j)
ll n;
vector<T> a;
AllPairOperationSum() {}
AllPairOperationSum(vector<T> a) : a(a), n(a.size()) {}
S add() {
// A + B
// O(N)
S ret = 0;
rep(i, 0, n) ret += a[i];
ret *= (n - 1);
return ret;
}
S sub() {
// A - B
// O(N)
S ret = 0;
rep(i, 0, n) ret += (S)(n - 1 - i * 2) * a[i];
return ret;
}
S mul() {
// A * B
// O(N)
S ret = 0;
vector<S> s(n);
s[0] = a[0];
rep(i, 1, n) {
s[i] = s[i - 1] + a[i];
ret += s[i - 1] * a[i];
}
return ret;
}
S div() {
// A / B (有理数mod)
// O(N log maxA)
S ret = 0;
vector<S> invs(n);
reverse(a.begin(), a.end());
invs[0] = (S)1 / a[0];
rep(i, 1, n) invs[i] = invs[i - 1] + (S)1 / a[i];
rep(i, 1, n) ret += invs[i - 1] * a[i];
reverse(a.begin(), a.end());
return ret;
}
T floor() {
// floor(A / B)
// O(N √maxA log maxA)
T maxa = *max_element(a.begin(), a.end());
T sqrtmaxa = sqrt(maxa);
vector<T> v(sqrtmaxa, 0);
fenwick_tree<T> ft(maxa + 1);
T ret = 0;
rep(i, 0, n) {
if (a[i] < sqrtmaxa) {
ret += v[a[i]];
} else {
for (T k = 0; k < maxa + 1; k += a[i]) {
ret += (k / a[i]) * ft.sum(k, std::min(k + a[i], maxa + 1));
}
}
ft.add(a[i], 1);
for (T j = 1; j < sqrtmaxa; j++) {
v[j] += a[i] / j;
}
}
return ret;
}
T mod() {
// A % B
// O(N √maxA log maxA)
T maxa = *max_element(a.begin(), a.end());
T sqrtmaxa = sqrt(maxa);
vector<T> v(sqrtmaxa, 0);
fenwick_tree<T> ft(maxa + 1);
T ret = 0;
rep(i, 0, n) {
if (a[i] < sqrtmaxa) {
ret += v[a[i]] * a[i];
} else {
for (T k = 0; k < maxa + 1; k += a[i]) {
ret += (k / a[i]) *
ft.sum(k, std::min(k + a[i], maxa + 1)) * a[i];
}
}
ft.add(a[i], 1);
for (T j = 1; j < sqrtmaxa; j++) {
v[j] += a[i] / j;
}
}
ret *= -1;
rep(i, 0, n) ret += (n - 1 - i) * a[i];
return ret;
}
S error_sq() {
// (A - B)^2
// O(N)
S ret = 0;
rep(i, 0, n) ret += (S)a[i] * a[i];
ret *= (n - 1);
ret += mul() * (-2);
return ret;
}
S max() {
// max(A, B)
// O(N)
S ret = 0;
vector<T> b = a;
sort(b.begin(), b.end());
rep(i, 0, n) ret += (S)i * b[i];
return ret;
}
S min() {
// min(A, B)
// O(N)
S ret = 0;
vector<T> b = a;
sort(b.rbegin(), b.rend());
rep(i, 0, n) ret += (S)i * b[i];
return ret;
}
S error() {
// |A - B|
// O(N)
S ret = 0;
vector<T> b = a;
sort(b.rbegin(), b.rend());
rep(i, 0, n) ret += (S)(n - 1 - i * 2) * b[i];
return ret;
}
S xor_() {
// A xor B
// O(N log maxA)
T mx = *max_element(a.begin(), a.end());
S ret = 0;
int base = 0;
while (mx >> base) {
vector<ll> cnt(2);
rep(i, 0, n) cnt[(a[i] >> base) & 1]++;
ret += (S)(1LL << base) * (cnt[0] * cnt[1]);
base++;
}
return ret;
}
S and_() {
// A & B
// O(N log maxA)
T mx = *max_element(a.begin(), a.end());
S ret = 0;
int base = 0;
while (mx >> base) {
vector<ll> cnt(2);
rep(i, 0, n) cnt[(a[i] >> base) & 1]++;
ret += (S)(1LL << base) * (cnt[1] * (cnt[1] - 1) / 2);
base++;
}
return ret;
}
S or_() {
// A | B
// O(N log maxA)
T mx = *max_element(a.begin(), a.end());
S ret = 0;
int base = 0;
while (mx >> base) {
vector<ll> cnt(2);
rep(i, 0, n) cnt[(a[i] >> base) & 1]++;
ret += (S)(1LL << base) *
(n * (n - 1) / 2 - cnt[0] * (cnt[0] - 1) / 2);
base++;
}
return ret;
}
S lcm() {
// lcm(A, B)
// O(maxA log maxA)
T m = *max_element(a.begin(), a.end());
vector<S> w(m + 1);
rep(i, 1, m + 1) {
w[i] += (S)1 / i;
int di = i + i;
while (di <= m) {
w[di] -= w[i];
di += i;
}
}
vector<ll> b(m + 1);
rep(i, 0, n) b[a[i]]++;
S ret = 0;
rep(i, 1, m + 1) {
ll di = i;
S sm = 0;
while (di <= m) {
sm += (S)b[di] * di;
di += i;
}
ret += (S)w[i] * sm * sm;
}
rep(i, 0, n) ret -= a[i];
ret /= 2;
return ret;
}
S gcd() {
// gcd(A, B)
// O(maxA log maxA)
T m = *max_element(a.begin(), a.end());
vector<S> w(m + 1);
rep(i, 1, m + 1) {
w[i] += i;
int di = i + i;
while (di <= m) {
w[di] -= w[i];
di += i;
}
}
vector<ll> b(m + 1);
rep(i, 0, n) b[a[i]]++;
S ret = 0;
rep(i, 1, m + 1) {
ll di = i;
S sm = 0;
while (di <= m) {
sm += b[di];
di += i;
}
ret += (S)w[i] * sm * sm;
}
rep(i, 0, n) ret -= a[i];
ret /= 2;
return ret;
}
};
int main() {
ll n;
cin >> n;
vector<int> a(n);
rep(i, 0, n) a[i] = i + 1;
reverse(a.begin(), a.end());
AllPairOperationSum<int> op(a);
ll ans = op.floor() + n;
cout << ans << endl;
}