Skip to content

Instantly share code, notes, and snippets.

@madhur4127
Last active June 6, 2020 13:55
Show Gist options
  • Save madhur4127/4eb29246463ed5a0538e1d9c8a2a7192 to your computer and use it in GitHub Desktop.
Save madhur4127/4eb29246463ed5a0538e1d9c8a2a7192 to your computer and use it in GitHub Desktop.
Infinite loop and high memory usage in GCC
#include "bits/stdc++.h"
using namespace std;
/////////////////// TYPES & MACROS ///////////////////////////////
#define all(x) x.begin(), x.end()
#define exist(s, e) (s.find(e) != s.end())
using i64 = int64_t;
using i32 = int32_t;
const char el = '\n';
template <class T>
constexpr inline i32 SZ(const T &x) { return x.size(); }
template <class T>
constexpr inline bool rmn(T &a, T b) { return a > b ? (a = b, true) : false; }
template <class T>
constexpr inline bool rmx(T &a, T b) { return a < b ? (a = b, true) : false; }
const i32 MOD = 1e9 + 7, INF = 0x3f3f3f3f;
const i64 INFLL = ((i64)INF << 32) | INF;
//////////////////// DEBUG /////////////////////////////////////////
#ifdef LOCAL
template <class... Args>
void dprint(Args... args) { ((std::cerr << args << ", "), ...) << el; }
#else
template <class... Args>
void dprint(Args... args) {}
#endif
template <class... Args>
void print(Args... args) { (std::cout << ... << args) << el; }
/////////////////// VARIABLES & FUNCTIONS//////////////////////////
vector<vector<i32>> adj;
vector<i32> vis, color;
template <int MOD = 1'000'000'007>
struct Modular {
int32_t value;
Modular(long long v = 0) {
value = v % MOD;
if (value < 0) value += MOD;
}
Modular(long long a, long long b) : value(0) {
*this += a;
*this /= b;
}
Modular &operator+=(Modular const &b) {
value += b.value;
if (value >= MOD) value -= MOD;
return *this;
}
Modular &operator-=(Modular const &b) {
value -= b.value;
if (value < 0) value += MOD;
return *this;
}
Modular &operator*=(Modular const &b) {
value = (long long)value * b.value % MOD;
return *this;
}
friend Modular mexp(Modular a, long long e) {
Modular res = 1;
while (e) {
if (e & 1) res *= a;
a *= a, e >>= 1;
}
return res;
}
friend Modular inverse(Modular a) {
int phi = MOD - 1; // change this for general MOD where a^phi = 1 (mod MOD)
return mexp(a, phi - 1);
}
Modular &operator/=(Modular const &b) { return *this *= inverse(b); }
friend Modular operator+(Modular a, const Modular b) { return a += b; }
friend Modular operator-(Modular a, const Modular b) { return a -= b; }
friend Modular operator-(const Modular a) { return 0 - a; }
friend Modular operator*(Modular a, const Modular b) { return a *= b; }
friend Modular operator/(Modular a, const Modular b) { return a /= b; }
friend std::ostream &operator<<(std::ostream &os, const Modular &a) { return os << a.value; }
friend std::istream &operator>>(std::istream &is, Modular &a) {
long long temp;
is >> temp;
a = Modular(temp);
return is;
}
friend bool operator==(Modular const &a, Modular const &b) { return a.value == b.value; }
friend bool operator!=(Modular const &a, Modular const &b) { return a.value != b.value; }
};
template <int N = 1'000'000, int MOD = 998244353>
struct combinatorics {
Modular<MOD> fac[N + 1], inv[N + 1];
constexpr combinatorics() : fac{}, inv{} {
fac[0] = 1;
for (int i = 1; i <= N; ++i)
fac[i] = i * fac[i - 1];
inv[N] = mexp(fac[N], MOD - 2);
for (int i = N - 1; i >= 0; i--)
inv[i] = (i + 1) * inv[i + 1];
}
int32_t factorial(int n) const { return fac[n]; }
int32_t inverse_factorial(int n) const { return inv[n]; }
int32_t nCr(int n, int r) const {
return (fac[n] * inv[r] * inv[n - r]).value;
}
};
///////////////////// MAIN STARTS //////////////////////////////////
int32_t main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
cout << fixed << setprecision(13), cerr << fixed << setprecision(3);
combinatorics<500'000, 998244353> obj;
int n, k;
cin >> n >> k;
Modular<998244353> ans = 0;
for (int i = 1; n / i >= k; ++i) {
ans += obj.nCr(n / i - 1, k - 1);
}
cout << ans << el;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment