Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace __gnu_pbds;
- using namespace std;
- //#define int long long
- #define pb push_back
- #define mp make_pair
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
- #pragma GCC target("avx,avx2")
- constexpr int INF = (int)1e9;
- constexpr int N = (int)5e7 + 111;
- constexpr int MAXN = (int)1e5 + 11;
- constexpr int md = (int)998244353;
- mt19937_64 rnd(std::chrono::steady_clock().now().time_since_epoch().count());
- template<class T>
- using ordered_multiset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
- template<class T>
- using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
- int bpow(int a,int b){
- if(b == 0)
- return 1;
- if(b % 2 == 0){
- int t = bpow(a,b>>1);
- return (1ll * t * t) % md;
- }
- return (1ll * a * bpow(a,b-1)) % md;
- }
- int inv(int a){
- return bpow(a,md-2);
- }
- int fac[N];
- int C(int n,int k){
- if(k > n)
- return 0;
- return (((1ll * fac[n] * inv(fac[k])) % md) * inv(fac[n-k])) % md;
- }
- void add(int& a,int b){
- a += b; if(a >= md) a -= md;
- }
- int f[N];
- int mn[N];
- vector<int> pr;
- void solve(){
- int n,c;
- cin >> n >> c;
- fac[0] = 1;
- for(int i = 1; i < N; i++){
- fac[i] = (1ll * fac[i-1] * i) % md;
- }
- for(int i = 2; i < N; i++){
- if(mn[i] == 0){
- mn[i] = i;
- pr.pb(i);
- }
- for(int j = 0; j < pr.size() && pr[j] <= mn[i] && i*pr[j] < N; j++)
- mn[i*pr[j]] = pr[j];
- }
- // return;
- int ans = 1;
- f[1] = 1;
- int precalc[33];
- for(int x = 1; x < 33; x++){
- precalc[x] = C(n-1+x,x);
- }
- int P[33];
- int ptr;
- for(int i = 2; i <= c; i++){
- int cnt = 0;
- int t = i;
- int p = mn[i];
- while(t > 1 && t % p == 0){
- t /= p;
- cnt++;
- }
- if(t == 1){
- f[i] = precalc[cnt];
- add(ans,f[i]);
- continue;
- }
- f[i] = (1ll * f[t] * f[i/t]) % md;
- add(ans,f[i]);
- // cerr << i << " " << f[i] << "\n";
- }
- cout << ans%md;
- return;
- }
- signed main(){
- ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
- int tests = 1;
- // cin >> tests;
- while(tests--){
- solve();
- }
- }
- /**
- ooo
- p^2
- 4
- 4 4 4
- 2 4 4
- 2 2 4
- 1 4 4
- 1 1 4
- 1 2 4
- C(n-1+d,d) = C(4,2) = 4!/2!2! = 24/4 = 6
- C(n-1+d,d)
- **/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement