#573427 (C++14) No.1276 3枚のカード

提出ソース

結果

問題	No.1276 3枚のカード
ユーザー	👑 Nachia
提出日時	2020-10-30 23:19:20
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	654 ms / 2,000 ms
コード長	2,732 bytes
コンパイル時間	1,583 ms
コンパイル使用メモリ	173,220 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-07-22 03:01:44
合計ジャッジ時間	21,552 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	549 ms 6,940 KB
testcase_11	AC	257 ms 6,940 KB
testcase_12	AC	329 ms 6,940 KB
testcase_13	AC	345 ms 6,940 KB
testcase_14	AC	31 ms 6,944 KB
testcase_15	AC	277 ms 6,940 KB
testcase_16	AC	599 ms 6,940 KB
testcase_17	AC	320 ms 6,940 KB
testcase_18	AC	242 ms 6,940 KB
testcase_19	AC	395 ms 6,944 KB
testcase_20	AC	229 ms 6,940 KB
testcase_21	AC	240 ms 6,940 KB
testcase_22	AC	610 ms 6,940 KB
testcase_23	AC	27 ms 6,940 KB
testcase_24	AC	376 ms 6,940 KB
testcase_25	AC	124 ms 6,944 KB
testcase_26	AC	464 ms 6,944 KB
testcase_27	AC	533 ms 6,940 KB
testcase_28	AC	514 ms 6,940 KB
testcase_29	AC	293 ms 6,944 KB
testcase_30	AC	56 ms 6,940 KB
testcase_31	AC	26 ms 6,940 KB
testcase_32	AC	133 ms 6,940 KB
testcase_33	AC	8 ms 6,944 KB
testcase_34	AC	91 ms 6,940 KB
testcase_35	AC	86 ms 6,944 KB
testcase_36	AC	6 ms 6,944 KB
testcase_37	AC	80 ms 6,940 KB
testcase_38	AC	52 ms 6,940 KB
testcase_39	AC	140 ms 6,940 KB
testcase_40	AC	583 ms 6,940 KB
testcase_41	AC	478 ms 6,940 KB
testcase_42	AC	521 ms 6,940 KB
testcase_43	AC	452 ms 6,944 KB
testcase_44	AC	645 ms 6,940 KB
testcase_45	AC	582 ms 6,940 KB
testcase_46	AC	588 ms 6,940 KB
testcase_47	AC	482 ms 6,940 KB
testcase_48	AC	460 ms 6,944 KB
testcase_49	AC	528 ms 6,940 KB
testcase_50	AC	581 ms 6,940 KB
testcase_51	AC	498 ms 6,944 KB
testcase_52	AC	423 ms 6,944 KB
testcase_53	AC	499 ms 6,944 KB
testcase_54	AC	576 ms 6,944 KB
testcase_55	AC	442 ms 6,944 KB
testcase_56	AC	427 ms 6,940 KB
testcase_57	AC	550 ms 6,940 KB
testcase_58	AC	572 ms 6,940 KB
testcase_59	AC	500 ms 6,944 KB
testcase_60	AC	654 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

template<ULL M>
struct static_modint {
    ULL x;
    static_modint(ULL val = 0) : x(val) {}

    static_modint& operator+=(static_modint r) { x += r.x; if (x >= M) x -= M; return *this; }
    static_modint operator+(static_modint r) const { static_modint res = x; return res += r; }
    static_modint& operator-=(static_modint r) { x += M - r.x; if (x >= M) x -= M; return *this; }
    static_modint operator-(static_modint r) const { static_modint res = x; return res -= r; }
    static_modint& operator*=(static_modint r) { x = x * r.x % M; return *this; }
    static_modint operator*(static_modint r) const { return static_modint(x * r.x % M); }
    static_modint pow(ULL r) const {
        if (r == 0) return static_modint(1);
        static_modint res = pow(r / 2);
        res *= res;
        if (r % 2) res *= *this;
        return res;
    }
    static_modint& operator/=(static_modint r) { *this *= r.pow(M - 2); return *this; }
    static_modint operator/(static_modint r) const { return *this * (r.pow(M - 2)); }
    ULL& operator*() { return x; }
    const ULL& operator*() const { return x; }
    bool operator==(static_modint r) const { return x == r; }
    bool operator!=(static_modint r) const { return x != r; }
};

static const ULL M = 1000000007;
using MLL = static_modint<M>;

vector<ULL> NMul; // number of greater multiples
vector<ULL> RNMul; // number of integers that has just the number of greater multiples

ULL F(ULL n) {
    ULL ans = 0;
    for (ULL i = 1; i * i <= n; i++) {
        ULL f = n / i;
        if (f * f > n) ans += f - 1;
    }
    for (ULL i = 1; i * i <= n; i++) ans += (i - 1) * (n / i - n / (i + 1));
    ans -= n - 1;
    return ans;
}

int main() {
    ULL N; cin >> N;

    NMul = { 0 };
    RNMul = {};

    for (ULL i = 1; i * i <= N; i++) {
        NMul.push_back(N / i - 1);
        if (NMul.back() * NMul.back() <= N) NMul.pop_back();
    }
    for (ULL i = 0; i * i <= N; i++) {
        RNMul.push_back(N / (i + 1) - N / (i + 2));
    }

    MLL ans = MLL(N % M) * MLL((N - 1) % M) * MLL((N - 2) % M);

    for (ULL i = 1; i < NMul.size(); i++) {
        MLL tmp = 0;
        tmp += (NMul[i] * (NMul[i] - 1) % M);
        tmp += ((N - 2) * (N - 1 - NMul[i]) % M);
        MLL Fx = F(NMul[i] + 1) % M;
        tmp += Fx;
        ans -= tmp;
    }
    for (ULL i = 0; i < RNMul.size(); i++) {
        MLL tmp = 0;
        tmp += (i * (i - 1) % M);
        tmp += ((N - 2) * (N - 1 - i) % M);
        MLL Fx = F(i + 1) % M;
        tmp += Fx;
        tmp *= RNMul[i];
        ans -= tmp;
    }

    cout << *ans << endl;

	return 0;
}

yukicoder

結果

テストケース

ソースコード