Submit Info #13511

Problem Lang User Status Time Memory
Sum of Floor of Linear cpp golikovnik AC 75 ms 1.80 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.72 MiB
random_00 AC 21 ms 0.96 MiB
random_01 AC 75 ms 1.80 MiB
random_02 AC 59 ms 1.60 MiB
random_03 AC 40 ms 1.28 MiB
random_04 AC 18 ms 0.86 MiB
small_00 AC 10 ms 0.73 MiB
small_01 AC 41 ms 1.04 MiB
small_02 AC 29 ms 0.94 MiB
small_03 AC 19 ms 0.80 MiB
small_04 AC 10 ms 0.80 MiB

// Copyright 2020 Nikita Golikov #include <bits/stdc++.h> using namespace std; using i64 = int64_t; using ui64 = uint64_t; #ifdef GOLIKOV mt19937_64 rng(566); #else mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); #endif template <typename T> T rnd_helper(T from, T to, true_type) { return uniform_int_distribution<T>(from, to)(rng); } template <typename T> T rnd_helper(T from, T to, false_type) { return uniform_real_distribution<T>(from, to)(rng); } template <typename T> T rnd(T from, T to) { return rnd_helper(from, to, is_integral<T>{}); } template <typename A, typename B, typename Cmp> bool set_min(A &x, B const &y, Cmp &&cmp) { if (cmp(y, x)) { x = y; return true; } return false; } template <typename A, typename B> bool set_min(A &x, B const &y) { return set_min(x, y, less<typename common_type<A, B>::type>{}); } template <typename A, typename B> bool set_max(A &x, B const &y) { return set_min(x, y, greater<typename common_type<A, B>::type>{}); } #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template <typename K, typename V> using ordered_map = tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>; // https://codeforces.com/blog/entry/62393 struct custom_hash { static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return static_cast<size_t>(splitmix64(x + FIXED_RANDOM)); } }; #ifdef __cpp_deduction_guides template <typename F> struct rec_fun { F fun; rec_fun(F &&fun_) : fun(std::forward<F>(fun_)) {} template <typename... Args> decltype(auto) operator()(Args &&... args) const { return fun(*this, std::forward<Args>(args)...); } }; #endif #ifdef __cpp_inline_variables template <typename T> inline constexpr auto type_min = numeric_limits<T>::lowest(); template <typename T> inline constexpr auto type_max = numeric_limits<T>::max(); #endif // fast alloc #if 0 int const MAX_MEM = 1e8; int mpos = 0; char mem[MAX_MEM]; void* operator new(size_t n) { mpos += n; return (void*)(mem + mpos - n); } void operator delete (void*) noexcept {} #endif // pragmas #if 0 #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4") #pragma GCC optimize("unroll-loops") #endif i64 calc(i64 n, i64 a, i64 b, i64 m) { if (a >= m || b >= m) { return (a / m) * n + (b / m) * n * (n - 1) / 2 + calc(n, a % m, b % m, m); } if (!b) { return 0; } return calc((a + b * n) / m, (a + b * n) % m, m, b); } int main() { #ifdef GOLIKOV assert(freopen("in", "rt", stdin)); auto _clock_start = chrono::high_resolution_clock::now(); #endif ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { i64 n, m, a, b; cin >> n >> m >> b >> a; cout << calc(n, a, b, m) << '\n'; } #ifdef GOLIKOV cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( chrono::high_resolution_clock::now() - _clock_start).count() << "ms." << endl; #endif return 0; }