#568423 (C++17) No.1260 たくさんの多項式

• 問題: No.1260 たくさんの多項式
• ユーザー: SHIJOU
• 提出日時: 2020-10-17 12:27:09
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 98 ms / 2,000 ms
• コード長: 3,186 bytes
• コンパイル時間: 1,840 ms
• コンパイル使用メモリ: 195,848 KB
• 最終ジャッジ日時: 2025-01-15 10:43:20
• ジャッジサーバーID （参考情報）: judge4 / judge5

ファイルパターン	結果
other	AC * 61

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 0xccccccc;
const ll LINF = 0xcccccccccccccccLL;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}
const unsigned int mod = 1000000007;
//const unsigned int mod = 998244353;
struct mint {
    unsigned int x;
    mint():x(0) {}
    mint(int64_t x_) {
        int64_t v = int64_t(x_ % mod);
        if(v < 0) v += mod;
        x = (unsigned int)v;
    }
    static mint row(int v) {
        mint v_;
        v_.x = v;
        return v_;
    }
    mint operator-() const { return mint(-int64_t(x));}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        uint64_t z = x;
        z *= a.x;
        x = (unsigned int)(z % mod);
        return *this;
    }
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    friend bool operator==(const mint &a, const mint &b) {return a.x == b.x;}
    friend bool operator!=(const mint &a, const mint &b) {return a.x != b.x;}
    mint &operator++() {
        x++;
        if(x == mod) x = 0;
        return *this;
    }
    mint &operator--() {
        if(x == 0) x = mod;
        x--;
        return *this;
    }
    mint operator++(int) {
        mint result = *this;
        ++*this;
        return result;
    }
    mint operator--(int) {
        mint result = *this;
        --*this;
        return result;
    }
    mint pow(int64_t t) const {
        mint x_ = *this, r = 1;
        while(t) {
            if(t&1) r *= x_;
            x_ *= x_;
            t >>= 1;
        }
        return r;
    }
    //for prime mod
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) {return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
string to_string(mint a) {
    return to_string(a.x);
}
//head
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    cin >> n;
    mint ans;
    int m = sqrt(n)+0.01;
    for(int i = 2; i <= m; i++) {
        ll u = n;
        while(u) {
            ans += u%i;
            u /= i;
        }
    }
    ll z = n/(m+1);
    ll zz = n/z+1;
    ans += (z*2+n%(m+1)+n%(zz-1))*(zz-m-1)>>1;
    const mint _ = mint(2).inv();
    for(int i = z-1; i > 0; i--) {
        z = n/(i+1)+1;
        zz = n/i+1;
        ans += mint(i*2+n%z+n%(zz-1))*(zz-z)*_;
    }
    cout << ans << endl;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX