This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ruthen71/rcpl
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2286" #include <bits/stdc++.h> #include "data_structure/cumulative_sum.hpp" #include "math/totient_table.hpp" int main() { auto ttt = totient_table(1000000); std::vector<long long> tl(ttt.size()); for (int i = 0; i < (int)ttt.size(); i++) tl[i] = ttt[i]; CumulativeSum<long long> rui(tl); int tt; std::cin >> tt; while (tt--) { int n; std::cin >> n; std::cout << rui.sum(0, n + 1) + 1 << '\n'; } return 0; }
#line 1 "verify/aoj_other/aoj_2286.test.cpp" #define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2286" #include <bits/stdc++.h> #line 2 "data_structure/cumulative_sum.hpp" template <class T> struct CumulativeSum { int n; std::vector<T> seg; CumulativeSum() = default; CumulativeSum(int n) : n(n), seg(n + 1, T(0)) {} CumulativeSum(std::vector<T> &a) { n = (int)a.size(); seg.assign(n + 1, T(0)); for (int i = 0; i < n; i++) seg[i + 1] = seg[i] + a[i]; } // [l, r) T sum(int l, int r) const { assert(0 <= l and l <= r and r <= n); return seg[r] - seg[l]; } // A[l] += x, A[l + 1] += x, ... , A[r - 1] += x void imos(int l, int r, T x = T(1)) { assert(0 <= l and l <= r and r <= n); seg[l] += x; seg[r] -= x; } void build() { for (int i = 0; i < n; i++) seg[i + 1] += seg[i]; } // return A[p] T get(int p) const { assert(0 <= p and p < n); return seg[p]; } // output friend std::ostream &operator<<(std::ostream &os, const CumulativeSum &A) { os << "n = " << A.n << "\n"; for (int i = 0; i <= A.n; i++) os << A.seg[i] << " \n"[i == A.n]; return os; } }; #line 2 "math/totient_table.hpp" std::vector<int> totient_table(int n) { std::vector<int> res(n + 1); std::iota(res.begin(), res.end(), 0); for (int p = 2; p <= n; p++) { if (res[p] != p) continue; for (int i = p; i <= n; i += p) { res[i] /= p; res[i] *= p - 1; } } return res; } #line 7 "verify/aoj_other/aoj_2286.test.cpp" int main() { auto ttt = totient_table(1000000); std::vector<long long> tl(ttt.size()); for (int i = 0; i < (int)ttt.size(); i++) tl[i] = ttt[i]; CumulativeSum<long long> rui(tl); int tt; std::cin >> tt; while (tt--) { int n; std::cin >> n; std::cout << rui.sum(0, n + 1) + 1 << '\n'; } return 0; }