結果

問題 No.3364 Push_back Operation
コンテスト
ユーザー tobisatis
提出日時 2025-11-17 22:23:44
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 1,393 ms / 2,000 ms
コード長 2,341 bytes
コンパイル時間 8,477 ms
コンパイル使用メモリ 171,580 KB
実行使用メモリ 187,800 KB
最終ジャッジ日時 2025-11-17 22:24:38
合計ジャッジ時間 37,191 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 53
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (97 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

#nullable enable

#region
var (_input, _iter) = (Array.Empty<string>(), 0);
T I<T>() where T : IParsable<T>
{
    while (_iter >= _input.Length) (_input, _iter) = (Console.ReadLine()!.Split(' '), 0);
    return T.Parse(_input[_iter++], null);
}
#endregion

var n = I<long>();
var s = 1L;
while (s * s <= n) s++;
s--;
ModInt ans = 0;
var last = n;
ModInt S(long i, ModInt k)
{
    if (k == 1) return i + 1;
    return (1 - k.Power(i + 1)) / (1 - k);
}
for (var i = 1; i <= s; i++)
{
    var j = n / (i + 1);
    ans += S(last, i) - S(j, i);
    last = j;
}

for (var i = 1; i <= n; i++)
{
    var j = n / i;
    if (j <= s) break;
    ans += ((ModInt)j).Power(i);
}
Console.WriteLine(ans);

readonly record struct ModInt
{
    public const int Mod = 998244353;
    int V { get; init; }
    public ModInt(long value)
    {
        var v = value % Mod;
        if (v < 0) v += Mod;
        V = (int)v;
    }
    static ModInt New(int value) => new(){ V = value };

    public static implicit operator ModInt(long v) => new(v);
    public static implicit operator int(ModInt modInt) => modInt.V;

    public static ModInt AdditiveIdentity => New(0);
    public static ModInt operator +(ModInt a, ModInt b)
    {
        var v = a.V + b.V;
        if (v >= Mod) v -= Mod;
        return New(v);
    }
    public ModInt AdditiveInverse()
    {
        if (V == 0) return AdditiveIdentity;
        return New(Mod - V);
    }
    public static ModInt operator -(ModInt a, ModInt b)
    {
        var v = a.V - b.V;
        if (v < 0) v += Mod;
        return New(v);
    }

    public static ModInt MultiplicativeIdentity => New(1);
    public static ModInt operator *(ModInt a, ModInt b) => New((int)((long)a.V * b.V % Mod));
    public ModInt MultiplicativeInverse() => V == 0 ? throw new DivideByZeroException() : Power(V, Mod - 2, Mod);
    public static ModInt operator /(ModInt a, ModInt b) => a * b.MultiplicativeInverse();

    static long Power(long v, ulong p, long mod)
    {
        var (res, k) = (1L, v);
        while (p > 0)
        {
            if ((p & 1) > 0) res = res * k % mod;
            k = k * k % mod;
            p >>= 1;
        }
        return res;
    }
    public ModInt Power(long p) => p < 0 ? MultiplicativeInverse().Power(-p) : Power(V, (ulong)p, Mod);

    public override string ToString() => V.ToString();
}
0