提出 #19723052


ソースコード 拡げる

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);
    auto z2=EuclidLike::calc(B, A-1, D,n);
    int ans = n - (z1.f - z2.f+mod)%mod;
    ans -= (A % D == 0);
    cout << ans << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T ;
    cin >> T;
    while (T--)
    {
        solve();
    }
}

提出情報

提出日時
問題 E - Simple Math 3
ユーザ NaCN
言語 C++ (GCC 9.2.1)
得点 0
コード長 2227 Byte
結果 WA
実行時間 50 ms
メモリ 3628 KB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 0 / 800
結果
AC × 1
AC × 16
WA × 5
セット名 テストケース
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
ケース名 結果 実行時間 メモリ
example_00 AC 11 ms 3528 KB
max_random_00 AC 50 ms 3588 KB
max_random_01 AC 44 ms 3624 KB
max_random_02 AC 45 ms 3596 KB
max_random_03 AC 45 ms 3516 KB
max_random_04 AC 44 ms 3584 KB
max_random_05 AC 48 ms 3464 KB
max_random_06 AC 45 ms 3532 KB
max_random_07 AC 45 ms 3536 KB
max_random_08 AC 44 ms 3460 KB
max_random_09 AC 48 ms 3464 KB
small_00 AC 30 ms 3624 KB
small_01 AC 29 ms 3520 KB
small_02 AC 30 ms 3504 KB
small_03 AC 26 ms 3516 KB
small_04 AC 31 ms 3456 KB
small_bc_00 WA 44 ms 3516 KB
small_bc_01 WA 47 ms 3460 KB
small_bc_02 WA 44 ms 3628 KB
small_bc_03 WA 41 ms 3532 KB
small_bc_04 WA 46 ms 3516 KB