結果

問題 No.2902 ZERO!!
ユーザー yamada
提出日時 2024-09-27 20:22:22
言語 C++23
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

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){
//ib
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0