Submission #19722868


Source Code Expand

Copy
#include <bits/stdc++.h>

using namespace std;
#define ll int64_
const int mod = 998244353, inv2 = (mod + 1) >> 1, inv6 = 166374059;

int inc(int x, int y) { return (x + y >= mod) ? (x + y - mod) : (x + y); }
int del(int x, int y) { return (x - y < 0) ? (x - y + mod) : (x - y); }

namespace EuclidLike
{
    struct Eans
    {
        int f, g, h;
    };
    Eans calc(int a, int b, int c, int n)
    {
        int s0 = n + 1;
        int s1 = 1ll * n * (n + 1) % mod * inv2 % mod;
        int s2 = 1ll * n * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod;
        if (!a)
        {
            int bz = b / c;
            int _f = 1ll * bz * s0 % mod;
            int _g = 1ll * bz * s1 % mod;
            int _h = 1ll * bz * bz % mod * s0 % mod;
            return {_f, _g, _h};
        }
        else if (a >= c || b >= c)
        {
            Eans tmp = calc(a % c, b % c, c, n);
            int bz = b / c, az = a / c;
            tmp.f = inc(tmp.f, inc(1ll * s1 * az, 1ll * s0 * bz % mod));
            tmp.g = inc(tmp.h, inc(1ll * az * s2 % mod, 1ll * bz * s1 % mod));
            tmp.h = inc(tmp.g, inc(inc(2ll * az * tmp.h % mod, 2ll * bz * tmp.f % mod), inc(inc(1ll * az * az % mod * s2 % mod, 2ll * az * bz % mod * s1 % mod), 1ll * bz * bz % mod * s0 % mod)));
            return tmp;
        }
        else
        {
            int m = (1ll * a * n + b) / c;
            Eans tmp = calc(c, c - b - 1, a, m - 1);
            int _f = del(1ll * n * m % mod, tmp.f);
            int _g = 1ll * del(del(1ll * n * (n + 1) % mod, tmp.f), tmp.h) * inv2 * mod;
            int _h = 1ll * del(1ll*n * m % mod * (m + 1) % mod, inc(inc(2ll * tmp.g % mod, 2ll * tmp.f % mod), _f));
            return {_f, _g, _h};
        }
    }
} // namespace EuclidLike

void solve()
{
    int A, B,C,D, n;
    cin >> A >> B >> C >>D;
     n = (D-2)/(C-B);
     
        
    auto z1=EuclidLike::calc(C, A, D,n)-A/D;
    auto z2=EuclidLike::calc(B, A-1, D,n)-(A-1)/D;
    int ans = n - (z1.f - z2.f);
    
    cout << ans << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T ;
    cin >> T;
    while (T--)
    {
        solve();
    }
}

Submission Info

Submission Time
Task E - Simple Math 3
User NaCN
Language C++ (GCC 9.2.1)
Score 0
Code Size 2228 Byte
Status CE

Compile Error

./Main.cpp: In function ‘void solve()’:
./Main.cpp:57:40: error: no match for ‘operator-’ (operand types are ‘EuclidLike::Eans’ and ‘int’)
   57 |     auto z1=EuclidLike::calc(C, A, D,n)-A/D;
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
      |                             |            |
      |                             |            int
      |                             EuclidLike::Eans
In file included from /usr/include/c++/9/bits/stl_algobase.h:67,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from ./Main.cpp:1:
/usr/include/c++/9/bits/stl_iterator.h:415:5: note: candidate: ‘template<class _IteratorL, class _IteratorR> constexpr decltype ((__y.base() - __x.base())) std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)’
  415 |     operator-(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/9/bits/stl_iterator.h:415:5: note:   template argument deduction/substitution failed:
./Main.cpp:57:43: note:   ‘EuclidLike::Eans’ is not derived from ‘const std::reverse_iterator<_Iterator>’
   57 |     auto z1=EuclidLike::calc(C, A, D,n)-A/D;
      |                                           ^
In file included from /usr/include/c++/9/bits/stl_algobase.h:67,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from ./Main.cpp:1:
/usr/include/c++/9/bits/stl_iterator.h:1212:5: note: candidate: ‘template<class _IteratorL, class _IteratorR> constexpr decltype ((__x.base() - __y.base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)’
 1212 |     operator-(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/9/bits/stl_iterator.h:1212:5: not...