fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. namespace std {
  6. #ifndef LOCAL
  7. #define cerr \
  8.   if (0) cerr
  9. #endif
  10.  
  11. template <typename T>
  12. T inverse(T a, T m) {
  13.   T u = 0, v = 1;
  14.   while (a != 0) {
  15.     T t = m / a;
  16.     m -= t * a;
  17.     swap(a, m);
  18.     u -= t * v;
  19.     swap(u, v);
  20.   }
  21.   assert(m == 1);
  22.   return u;
  23. }
  24.  
  25. template <typename T>
  26. class Modular {
  27.  public:
  28.   using Type = typename decay<decltype(T::value)>::type;
  29.  
  30.   constexpr Modular() : value() {}
  31.   template <typename U>
  32.   Modular(const U& x) {
  33.     value = normalize(x);
  34.   }
  35.  
  36.   template <typename U>
  37.   static Type normalize(const U& x) {
  38.     Type v;
  39.     if (-mod() <= x && x < mod())
  40.       v = static_cast<Type>(x);
  41.     else
  42.       v = static_cast<Type>(x % mod());
  43.     if (v < 0) v += mod();
  44.     return v;
  45.   }
  46.  
  47.   const Type& operator()() const { return value; }
  48.   template <typename U>
  49.   explicit operator U() const { return static_cast<U>(value); }
  50.   constexpr static Type mod() { return T::value; }
  51.  
  52.   Modular& operator+=(const Modular& other) {
  53.     if ((value += other.value) >= mod()) value -= mod();
  54.     return *this;
  55.   }
  56.   Modular& operator-=(const Modular& other) {
  57.     if ((value -= other.value) < 0) value += mod();
  58.     return *this;
  59.   }
  60.   template <typename U>
  61.   Modular& operator+=(const U& other) { return *this += Modular(other); }
  62.   template <typename U>
  63.   Modular& operator-=(const U& other) { return *this -= Modular(other); }
  64.   Modular& operator++() { return *this += 1; }
  65.   Modular& operator--() { return *this -= 1; }
  66.   Modular operator++(int) {
  67.     Modular result(*this);
  68.     *this += 1;
  69.     return result;
  70.   }
  71.   Modular operator--(int) {
  72.     Modular result(*this);
  73.     *this -= 1;
  74.     return result;
  75.   }
  76.   Modular operator-() const { return Modular(-value); }
  77.  
  78.   template <typename U = T>
  79.   typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
  80. #ifdef _WIN32
  81.     uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
  82.     uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
  83.     asm(
  84.         "divl %4; \n\t"
  85.         : "=a"(d), "=d"(m)
  86.         : "d"(xh), "a"(xl), "r"(mod()));
  87.     value = m;
  88. #else
  89.     value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
  90. #endif
  91.     return *this;
  92.   }
  93.   template <typename U = T>
  94.   typename enable_if<is_same<typename Modular<U>::Type, long long>::value, Modular>::type& operator*=(const Modular& rhs) {
  95.     long long q = static_cast<long long>(static_cast<long double>(value) * rhs.value / mod());
  96.     value = normalize(value * rhs.value - q * mod());
  97.     return *this;
  98.   }
  99.   template <typename U = T>
  100.   typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
  101.     value = normalize(value * rhs.value);
  102.     return *this;
  103.   }
  104.  
  105.   Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }
  106.  
  107.   friend const Type& abs(const Modular& x) { return x.value; }
  108.  
  109.   template <typename U>
  110.   friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
  111.  
  112.   template <typename U>
  113.   friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
  114.  
  115.   template <typename V, typename U>
  116.   friend V& operator>>(V& stream, Modular<U>& number);
  117.  
  118.  private:
  119.   Type value;
  120. };
  121.  
  122. template <typename T>
  123. bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
  124. template <typename T, typename U>
  125. bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
  126. template <typename T, typename U>
  127. bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }
  128.  
  129. template <typename T>
  130. bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
  131. template <typename T, typename U>
  132. bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
  133. template <typename T, typename U>
  134. bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
  135.  
  136. template <typename T>
  137. bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }
  138.  
  139. template <typename T>
  140. Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
  141. template <typename T, typename U>
  142. Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
  143. template <typename T, typename U>
  144. Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
  145.  
  146. template <typename T>
  147. Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
  148. template <typename T, typename U>
  149. Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
  150. template <typename T, typename U>
  151. Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
  152.  
  153. template <typename T>
  154. Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
  155. template <typename T, typename U>
  156. Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
  157. template <typename T, typename U>
  158. Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
  159.  
  160. template <typename T>
  161. Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
  162. template <typename T, typename U>
  163. Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
  164. template <typename T, typename U>
  165. Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
  166.  
  167. template <typename T, typename U>
  168. Modular<T> power(const Modular<T>& a, const U& b) {
  169.   assert(b >= 0);
  170.   Modular<T> x = a, res = 1;
  171.   U p = b;
  172.   while (p > 0) {
  173.     if (p & 1) res *= x;
  174.     x *= x;
  175.     p >>= 1;
  176.   }
  177.   return res;
  178. }
  179.  
  180. template <typename T>
  181. bool IsZero(const Modular<T>& number) {
  182.   return number() == 0;
  183. }
  184.  
  185. template <typename T>
  186. string to_string(const Modular<T>& number) {
  187.   return to_string(number());
  188. }
  189.  
  190. // U == std::ostream? but done this way because of fastoutput
  191. template <typename U, typename T>
  192. U& operator<<(U& stream, const Modular<T>& number) {
  193.   return stream << number();
  194. }
  195.  
  196. // U == std::istream? but done this way because of fastinput
  197. template <typename U, typename T>
  198. U& operator>>(U& stream, Modular<T>& number) {
  199.   typename common_type<typename Modular<T>::Type, long long>::type x;
  200.   stream >> x;
  201.   number.value = Modular<T>::normalize(x);
  202.   return stream;
  203. }
  204.  
  205. /*
  206. using ModType = int;
  207.  
  208. struct VarMod { static ModType value; };
  209. ModType VarMod::value;
  210. ModType& md = VarMod::value;
  211. using Mint = Modular<VarMod>;
  212. */
  213.  
  214. constexpr int md = (int)1e9 + 7;
  215. using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
  216.  
  217. /*vector<Mint> fact(1, 1);
  218. vector<Mint> inv_fact(1, 1);
  219.  
  220. Mint C(int n, int k) {
  221.         if (k < 0 || k > n) {
  222.                 return 0;
  223.         }
  224.         while ((int) fact.size() < n + 1) {
  225.                 fact.push_back(fact.back() * (int) fact.size());
  226.                 inv_fact.push_back(1 / fact.back());
  227.         }
  228.         return fact[n] * inv_fact[k] * inv_fact[n - k];
  229. }*/
  230.  
  231. }  // namespace std
  232.  
  233. vector<int> uoc[500005];
  234. Mint cnt[500005];
  235.  
  236. int32_t main() {
  237.   ios_base::sync_with_stdio(0);
  238.   cin.tie(0);
  239. #ifdef LOCAL
  240. #define task "a"
  241. #else
  242. #define task "GCDS"
  243. #endif
  244.   if (fopen(task ".inp", "r")) {
  245.     freopen(task ".inp", "r", stdin);
  246.     freopen(task ".out", "w", stdout);
  247.   }
  248.   int n, q;
  249.   cin >> n >> q;
  250.   vector<int> a(n);
  251.   vector<pair<int, int>> qr(q);
  252.   int mx = 0;
  253.   for (int& x : a) {
  254.     cin >> x;
  255.     mx = max(mx, x);
  256.   }
  257.   for (auto& [x, y] : qr) {
  258.     cin >> x >> y;
  259.     x--;
  260.     mx = max(mx, y);
  261.   }
  262.   for (int i = 1; i <= mx; i++) {
  263.     for (int j = i; j <= mx; j += i) {
  264.       uoc[j].push_back(i);
  265.     }
  266.   }
  267. 	vector<Mint> r(mx + 1);
  268. 	r[1] = 1;
  269. 	for (int i = 2; i <= mx; i++) {
  270. 		r[i] = md - (md / i) * r[md % i];
  271. 	}
  272.   Mint tot = 0;
  273.   auto add = [&](int x, int delta) {
  274.     for (auto it : uoc[x]) {
  275.       if (delta > 0) {
  276.         tot += cnt[it] * r[it] * x * r[it] * delta;
  277.         cnt[it] += delta * x;
  278.       } else {
  279.         cnt[it] += delta * x;
  280.         tot += cnt[it] * r[it] * x * r[it] * delta;
  281.       }
  282.     }
  283.   };
  284.   vector<int> freq(mx + 1, 0);
  285.   for (int x : a) {
  286.     ++freq[x];
  287.   }
  288.   for (int i = 1; i <= mx; i++) {
  289.     if (freq[i]) {
  290.       add(i, freq[i]);
  291.       int64_t npairs = 1ll * (freq[i]) * (freq[i] - 1) / 2;
  292.       for (int j : uoc[i]) {
  293.         tot += Mint(npairs) * (i / j) * (i / j);
  294.       }
  295.     }
  296.   }
  297.   cout << tot << '\n';
  298.   for (auto [x, y] : qr) {
  299.       if (a[x] != y) {
  300.     add(a[x], -1);
  301.     a[x] = y;
  302.     add(a[x], 1);
  303.       }
  304.     cout << tot << '\n';
  305.   }
  306.   return 0;
  307. }
  308.  
Success #stdin #stdout 0.01s 17212KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/cjrYwQ
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!