結果

問題 No.2902 ZERO!!
ユーザー yamadayamada
提出日時 2024-09-27 20:22:22
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 124 ms / 2,000 ms
コード長 3,644 bytes
コンパイル時間 4,196 ms
コンパイル使用メモリ 210,140 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-27 20:22:30
合計ジャッジ時間 7,299 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 8 ms
6,816 KB
testcase_01 AC 8 ms
6,940 KB
testcase_02 AC 124 ms
6,948 KB
testcase_03 AC 9 ms
6,944 KB
testcase_04 AC 33 ms
6,944 KB
testcase_05 AC 63 ms
6,944 KB
testcase_06 AC 117 ms
6,940 KB
testcase_07 AC 40 ms
6,940 KB
testcase_08 AC 110 ms
6,940 KB
testcase_09 AC 108 ms
6,944 KB
testcase_10 AC 81 ms
6,944 KB
testcase_11 AC 67 ms
6,940 KB
testcase_12 AC 15 ms
6,944 KB
testcase_13 AC 109 ms
6,940 KB
testcase_14 AC 85 ms
6,940 KB
testcase_15 AC 96 ms
6,944 KB
testcase_16 AC 59 ms
6,944 KB
testcase_17 AC 106 ms
6,940 KB
testcase_18 AC 101 ms
6,940 KB
testcase_19 AC 90 ms
6,940 KB
testcase_20 AC 78 ms
6,940 KB
testcase_21 AC 83 ms
6,940 KB
testcase_22 AC 45 ms
6,940 KB
testcase_23 AC 61 ms
6,944 KB
testcase_24 AC 9 ms
6,940 KB
testcase_25 AC 9 ms
6,940 KB
testcase_26 AC 9 ms
6,940 KB
testcase_27 AC 9 ms
6,940 KB
testcase_28 AC 9 ms
6,940 KB
testcase_29 AC 9 ms
6,940 KB
testcase_30 AC 9 ms
6,944 KB
testcase_31 AC 9 ms
6,940 KB
testcase_32 AC 9 ms
6,944 KB
testcase_33 AC 9 ms
6,944 KB
testcase_34 AC 9 ms
6,944 KB
testcase_35 AC 9 ms
6,940 KB
testcase_36 AC 9 ms
6,940 KB
testcase_37 AC 9 ms
6,940 KB
testcase_38 AC 9 ms
6,940 KB
testcase_39 AC 9 ms
6,944 KB
testcase_40 AC 9 ms
6,940 KB
testcase_41 AC 9 ms
6,944 KB
testcase_42 AC 8 ms
6,940 KB
testcase_43 AC 9 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <map>
#include <stack>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <bitset>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define rrep(i,a,b) for(ll i=a;i>=b;--i)
#define fore(i, a) for(auto& i : a)
#define pi 3.141592653589793238
typedef long long ll;
typedef pair<ll,ll> pp;
typedef vector<ll> vl;
typedef vector<ulong> vu;
typedef vector<vl> vvl;
typedef vector<pp> vp;
typedef vector<vp> vvp;
typedef priority_queue<pp, vp, greater<pp> > pq;
vl kaijou;
void kaijou_set(ll m) {kaijou.push_back(1); rep(i, 1, 1000009)kaijou.push_back((kaijou[i-1] * i) % m); return;}
ll C(ll a, ll b, ll m) {if(a<b||b<0) return 0; return (kaijou[a] * pow_mod(kaijou[a-b] * kaijou[b], m-2, m)) % m;}
template <typename T, typename F>
T bisect(T ok, T bad, F pred) {if(!pred(ok))return ok; while (bad - ok > 1) {T mid = ok + (bad - ok) / 2; (pred(mid) ? ok : bad) = mid;} return bad;}
bool chmin(ll &a, ll b) {if (a > b) {a = b;return true;} return false;}
bool chmax(ll &a, ll b) {if (a < b) {a = b;return true;} return false;}
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
ll gcd(ll x, ll y) {if(y == 0)return x; return gcd(y, x % y); }
ll RU(ll a, ll b) {return a / b + (a % b && (a ^ b) >= 0); }
ll minus_mod(ll a,ll m){return a < 0 ? (a + RU(abs(a), m) * m) % m : a % m; }
ll mod=998244353; ll mof=1000000007;

vector<int> pri;
void pri_set()
{
    if(!pri.empty()) return;
    bool sos[1000009];
    for (int i = 2; i < 1000009; ++i) sos[i] = true;
    sos[1] = false;
    sos[0] = false;

    for (int i = 2; i < 1000009; ++i)
    {
        if (sos[i])
        {
            for (ll j = 2; i * j < 1000009; j++) sos[i * j] = false;
            pri.push_back(i);
        }
    }
    return;
}
vector<pair<long long, long long>> prime_factorize(long long m)
{
    long long M = m;
    vector<pair<long long, long long>> ans;
    pri_set();
    for (int i = 0; i < pri.size(); ++i)
    {
        if (M % pri[i] == 0)
            ans.push_back(make_pair(pri[i], 0));
        while (M % pri[i] == 0)
        {
            M /= pri[i];
            ++ans[ans.size() - 1].second;
        }
    }
    if (M > 1)
        ans.push_back(make_pair(M, 1));
    return ans;
}
void dfs(ll val, ll dep, vector<long long> &ans, vector<pair<long long, long long>> prime)
{
    if (dep == prime.size())
    {
        ans.push_back(val);
        return;
    }
    ll so = 1;
    for (int i = 0; i <= prime[dep].second; ++i)
    {
        dfs(val * so, dep + 1, ans, prime);
        so *= prime[dep].first;
    }
    return;
}
vector<long long> div_enum(long long m)
{
    vector<long long> ans;
    vector<pair<long long, long long>> prime = prime_factorize(m);
    dfs(1, 0, ans, prime);
    sort(ans.begin(), ans.end());
    return ans;
}


int main() 
{
    ll n;cin>>n;
    pri_set();
    vl cnt(pri.size());

    rep(i,0,pri.size()){
        ll nkari=n;
        cnt[i]=0;
        ll m=pri[i];
        while(m<=n){
            cnt[i]+=n/m;
            m*=pri[i];
        }
    }

    ll ans=0;
    
    rep(i,1,mof){
        //i回割れるbがいくつあるか
        ll anskari=1;
        rep(j,0,cnt.size()){
            ll lim=cnt[j]/i;//素因数jを含ませていい回数
            if(lim==0)break;
            anskari*=lim+1;
            anskari%=mod;
        }
        anskari+=mod-1;anskari%=mod;
        if(anskari==0)break;
        ans+=anskari;ans%=mod;
    }
    cout<<ans<<endl;
}
0