Submission #616086

---

Source Code Expand

#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>

#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>

using namespace std;
#define all(c) begin(c), end(c)
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

ll gcd(ll a, ll b) {
    return b ? gcd(b, a%b) : a;
}
ll lcm(ll a, ll b) {
    return a / gcd(a, b)*b;
}
ll popcount(ll x) {
    return x ? x % 2 + popcount(x / 2) : x;
}
ll solve(ll n) {
    ll nico = 25;
    ll ans = 0;
    vector<ll> nicos;
    while (nico <= n) {
        nicos.emplace_back(nico);
        nico = nico * 100 + 25;
    }
    int sz = nicos.size();
    for (int S = 1; S < 1 << sz; S++) {
        int c = popcount(S);
        ll x = 1;
        for (int i = 0; i < sz; i++) {
            if (S >> i & 1) x = lcm(x, nicos[i]);
            if (x > n) goto END;
        }
        if (c & 1) {
            ans -= n/x;
        } else {
            ans += n/x;
        }
    END:;
    }
    return -ans;
}

int main() {
    ll n;
    while (cin >> n) {
        cout << solve(n) << endl;
    }
}

Submission Info

Judge Result