Submission #19722922


Source Code Expand

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

using namespace std;
#define ll int64_t
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
{
    ll calc(ll a, ll b, ll c, ll n)
{
    if (a == 0)
        return (n + 1) * (b / c);
    if (a >= c || b >= c)
        return (calc(a % c, b % c, c, n) + (a / c) * n * (n + 1) / 2 + (b / c) * (n + 1));
    ll m = (a * n + b) / c;
    return (n * m - calc(c, c - b - 1, a, m - 1));
}

} // 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 - z2);
    
    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 800
Code Size 1058 Byte
Status AC
Exec Time 42 ms
Memory 3624 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 800 / 800
Status
AC × 1
AC × 21
Set Name Test Cases
Sample example_00
All example_00, max_random_00, max_random_01, max_random_02, max_random_03, max_random_04, max_random_05, max_random_06, max_random_07, max_random_08, max_random_09, small_00, small_01, small_02, small_03, small_04, small_bc_00, small_bc_01, small_bc_02, small_bc_03, small_bc_04
Case Name Status Exec Time Memory
example_00 AC 6 ms 3520 KB
max_random_00 AC 42 ms 3516 KB
max_random_01 AC 37 ms 3516 KB
max_random_02 AC 36 ms 3592 KB
max_random_03 AC 36 ms 3588 KB
max_random_04 AC 40 ms 3460 KB
max_random_05 AC 36 ms 3580 KB
max_random_06 AC 40 ms 3624 KB
max_random_07 AC 36 ms 3528 KB
max_random_08 AC 36 ms 3508 KB
max_random_09 AC 38 ms 3460 KB
small_00 AC 28 ms 3460 KB
small_01 AC 26 ms 3512 KB
small_02 AC 25 ms 3620 KB
small_03 AC 29 ms 3592 KB
small_04 AC 28 ms 3508 KB
small_bc_00 AC 39 ms 3596 KB
small_bc_01 AC 37 ms 3592 KB
small_bc_02 AC 38 ms 3512 KB
small_bc_03 AC 40 ms 3528 KB
small_bc_04 AC 37 ms 3516 KB