結果
| 問題 |
No.3136 F,B in FizzBuzzString16
|
| ユーザー |
 ecottea
|
| 提出日時 | 2025-05-04 15:53:44 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 14,910 bytes |
| コンパイル時間 | 4,815 ms |
| コンパイル使用メモリ | 256,620 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-04 15:53:51 |
| 合計ジャッジ時間 | 5,590 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 7 |
| other | AC * 32 |
ソースコード
#ifndef HIDDEN_IN_VS // 折りたたみ用
// 警告の抑制
#define _CRT_SECURE_NO_WARNINGS
// ライブラリの読み込み
#include <bits/stdc++.h>
using namespace std;
// 型名の短縮
using ll = long long; using ull = unsigned long long; // -2^63 ～ 2^63 = 9e18（int は -2^31 ～ 2^31 = 2e9）
using pii = pair<int, int>; using pll = pair<ll, ll>; using pil = pair<int, ll>; using pli = pair<ll, int>;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vvvvi = vector<vvvi>;
using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>; using vvvvl = vector<vvvl>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vc = vector<char>; using vvc = vector<vc>; using vvvc = vector<vvc>;
using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;
template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
using Graph = vvi;
// 定数の定義
const double PI = acos(-1);
int DX[4] = { 1, 0, -1, 0 }; // 4 近傍（下，右，上，左）
int DY[4] = { 0, 1, 0, -1 };
int INF = 1001001001; ll INFL = 4004004003094073385LL; // (int)INFL = INF, (int)(-INFL) = -INF;
// 入出力高速化
struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp;
// 汎用マクロの定義
#define all(a) (a).begin(), (a).end()
#define sz(x) ((int)(x).size())
#define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), (x)))
#define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), (x)))
#define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");}
#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順
#define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順
#define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順
#define repe(v, a) for(const auto& v : (a)) // a の全要素（変更不可能）
#define repea(v, a) for(auto& v : (a)) // a の全要素（変更可能）
#define repb(set, d) for(int set = 0, set##_ub = 1 << int(d); set < set##_ub; ++set) // d ビット全探索（昇順）
#define repis(i, set) for(int i = lsb(set), bset##i = set; i < 32; bset##i -= 1 << i, i = lsb(bset##i)) // set の全要素（昇順）
#define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て（昇順）
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去
#define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了
#define inQ(x, y, u, l, d, r) ((u) <= (x) && (l) <= (y) && (x) < (d) && (y) < (r)) // 半開矩形内判定
// 汎用関数の定義
template <class T> inline ll powi(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; }
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新（更新されたら true を返す）
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新（更新されたら true を返す）
template <class T> inline T getb(T set, int i) { return (set >> i) & T(1); }
template <class T> inline T smod(T n, T m) { n %= m; if (n < 0) n += m; return n; } // 非負mod
// 演算子オーバーロード
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repea(x, v) is >> x; return is; }
template <class T> inline vector<T>& operator--(vector<T>& v) { repea(x, v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { repea(x, v) ++x; return v; }
#endif // 折りたたみ用
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#ifdef _MSC_VER
#include "localACL.hpp"
#endif
using mint = modint998244353;
//using mint = static_modint<(int)1e9 + 7>;
//using mint = modint; // mint::set_mod(m);
namespace atcoder {
inline istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; }
inline ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; }
}
using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>; using vvvvm = vector<vvvm>; using pim = pair<int, mint>;
#endif
#ifdef _MSC_VER // 手元環境（Visual Studio）
#include "local.hpp"
#else // 提出用（gcc）
inline int popcount(int n) { return __builtin_popcount(n); }
inline int popcount(ll n) { return __builtin_popcountll(n); }
inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : 32; }
inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : 64; }
inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; }
inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; }
#define dump(...)
#define dumpel(v)
#define dump_math(v)
#define input_from_file(f)
#define output_to_file(f)
#define Assert(b) { if (!(b)) { vc MLE(1<<30); EXIT(MLE.back()); } } // RE の代わりに MLE を出す
#endif
//【めぐる式二分探索】O(log|ok - ng|)
/*
* 条件 okQ() を満たす要素 ok と満たさない要素 ng との境界を二分探索する．
* 境界に隣り合うような条件を満たす要素（ok 側）の位置を返す．
* debug_mode = true にして実行すると手元では単調かどうかチェックしながら全探索する．
*/
template <class T, class FUNC>
T meguru_search(T ok, T ng, const FUNC& okQ, bool debug_mode = false) {
// 参考 : https://twitter.com/meguru_comp/status/697008509376835584
// verify : https://atcoder.jp/contests/typical90/tasks/typical90_a
Assert(ok != ng);
#ifdef _MSC_VER
// 単調かどうか自信がないとき用
if (debug_mode) {
T step = ok < ng ? 1 : -1; T res = ok; bool is_ok = true;
for (T i = ok; i != ng + step; i += step) {
auto b = okQ(i);
if (b) {
if (!is_ok) {
cout << "not monotony!" << endl;
for (T i = ok; i != ng + step; i += step) {
cout << i << " : " << okQ(i) << endl;
}
exit(1);
}
}
else {
if (is_ok) res = i - step;
is_ok = false;
}
}
return res;
}
#endif
// 境界が決定するまで
while (abs(ok - ng) > 1) {
// 区間の中間
T mid = (ok + ng) / 2;
// 中間が OK かどうかに応じて区間を縮小する．
if (okQ(mid)) ok = mid;
else ng = mid;
}
return ok;
/* okQ の定義の雛形
auto okQ = [&](ll x) {
return true || false;
};
*/
}
//【連続整数の剰余の数え上げ】O(1)
/*
* x∈[l..r) で x ≡ k (mod m) を満たすものの個数を返す．
*/
template <class T>
T count_by_mod(T l, T r, T m, T k) {
// verify : https://atcoder.jp/contests/abc334/tasks/abc334_b
//【方法】
// l = k (mod m) になるように l を増加させても答えは変わらない．
// こうすれば個数は [0..n) 内の m の倍数の数え上げと同様に考えて
// (r - l + m - 1) / m
// で求められる．
Assert(m > 0);
if (l >= r) return 0;
k = smod(k, m);
l -= k;
T l2 = l + smod(-l, m);
l2 += k;
return (r - l2 + m - 1) / m;
}
//【一次式の切り捨て和】O(log(n + m))
/*
* Σi∈[0..n) floor((a i + b) / m) を返す．
*/
template <class T>
T arithmetic_floor_sum(T n, T m, T a, T b) {
// 参考 : https://twitter.com/kyopro_friends/status/1304063876019793921?ref_src=twsrc%5Etfw
// verify : https://judge.yosupo.jp/problem/sum_of_floor_of_linear
//【方法】
// m < 0 なら a, b, m をそれぞれ -1 倍して m > 0 とする．
// a = aq m + ar, b = bq m + br (0 ≦ ar, br < m)
// と表すと，
// Σi∈[0..n) floor((a i + b) / m)
// = Σi∈[0..n) (floor((ar i + br) / m) + (aq i + bq))
// = Σi∈[0..n) floor((ar i + br) / m) + (aq n(n-1)/2 + bq n)
// となるので 0 ≦ a < m, 0 ≦ b < m として一般性を失わない．
//
// 求めるべき値は，領域
// {(x, y) | 0 ≦ x < n かつ 0 < y ≦ (a x + b) / m}
// に含まれる格子点の個数である．u1 = floor((a x + b) / m) とおき，変数変換
// v = n - x, u = u1 - y
// を施すと，直線 y = (a x + b) / m の式は
// u1 - u = (a (n - v) + b) / m
// ⇔ m u1 - m u = a n - a v + b
// ⇔ a v = m u + a n + b - m u1
// ⇔ v = (m u + (a n + b - m u1)) / a
// と書き換えられるので，先の領域は
// {(u, v) | 0 ≦ u < u1 かつ 0 < v ≦ (m u + (a n + b - m u1)) / a}
// となる．ここに含まれる格子点の個数は
// Σi∈[0..u1) floor((m i + (a n + b - m u1)) / a)
// であり，分母を m からより小さい a に書き換えられた．
//
// 次のステップに進む前に m ← m mod a とするので，収束の速さはユークリッドの互除法と同じである．
Assert(m != 0);
if (n <= 0) return 0;
T res = 0;
// m < 0 の場合，分母分子を -1 倍して m > 0 とする．
if (m < 0) { a *= -1; b *= -1; m *= -1; }
// a を m だけ増減させた場合の影響は floor なしの和で計算できるので，0 ≦ a < m とする．
res += (a / m - (T)(a % m < 0)) * (n * (n - 1) / 2);
a = smod(a, m);
// b を m だけ増減させた場合の影響は floor なしの和で計算できるので，0 ≦ b < m とする．
res += (b / m - (T)(b % m < 0)) * n;
b = smod(b, m);
while (a > 0) {
T nn = (a * n + b) / m;
T nm = a;
T na = m;
T nb = a * n + b - m * nn;
res += (na / nm) * (nn * (nn - 1) / 2);
na %= nm;
res += (nb / nm) * nn;
nb %= nm;
n = nn; m = nm; a = na; b = nb;
}
return res;
}
//【一次式の剰余の数え上げ（範囲指定）】O(log(n + m))
/*
* 各 i∈[0..n) に対する (a i + b) mod m のうち，値が [l..r) に属するものの個数を返す．
*
* 利用：【一次式の切り捨て和】
*/
template <class T>
T count_arithmetic_mod(T n, T m, T a, T b, T l, T r) {
// 参考 : https://twitter.com/maspy_stars/status/1649421402573766656
// verify : https://yukicoder.me/problems/no/2280
//【方法】
// 条件を同値変形していくと，
// l ≦ (ai+b) mod m < r
// ⇔ l ≦ (ai+b) - floor((ai+b)/m) * m < r
// ⇔ (ai+b-l)/m ≧ floor((ai+b)/m) > (ai+b-r)/m
// となる．中辺が整数であることと
// (左辺) - (右辺) = (r-l)/m ≦ 1
// であることに注意すると，
// (ai+b) mod m ∈ [l..r) ⇔ floor((ai+b-l)/m) - floor((ai+b-r)/m) = 1
// (ai+b) mod m !∈ [l..r) ⇔ floor((ai+b-l)/m) - floor((ai+b-r)/m) = 0
// が分かる．よって floor_sum の差を取れば良い．
Assert(m > 0);
if (n <= 0) return 0;
chmax(l, T(0)); chmin(r, m);
if (l >= r) return 0;
a = smod(a, m); b = smod(b, m);
T res = arithmetic_floor_sum(n, m, a, b - l);
res -= arithmetic_floor_sum(n, m, a, b - r);
return res;
}
//【桁の数の取得】O(log n)
/*
* n を b 進表記したときの桁の数字を上位桁から順に並べたリストを返す．
*
* 制約：b ≧ 2
*/
vi integer_digits(ll n, int b = 10) {
// verify : https://atcoder.jp/contests/abc105/tasks/abc105_c
Assert(abs(b) >= 2);
// n = 0 の場合の例外処理
if (n == 0) return vi{ 0 };
// mod |b| を取れば最下位桁から順に決定していく．
vi ds;
while (n != 0) {
int d = (int)(n % b);
//int d = (int)smod(n, abs(b)); // 負数の可能性があるならこっち
ds.push_back(d);
n = (n - d) / b;
}
// 上位桁から順になるように並べ直す．
reverse(all(ds));
return ds;
}
ll solve(ll Len) {
int D = 10;
vl pow16(D + 1);
pow16[0] = 1;
repi(d, 1, D) pow16[d] = pow16[d - 1] * 16;
// 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz B Fizz D E FizzBuzz 10 ...
auto get_len = [&](ll n) {
ll len = 0;
// d : 桁数
repi(d, 1, D) {
ll lb = pow16[d - 1];
ll ub = min(pow16[d], n + 1);
if (lb >= ub) break;
// 除原理
ll c15 = count_by_mod<ll>(lb, ub, 15, 0);
ll c5 = count_by_mod<ll>(lb, ub, 5, 0) - c15;
ll c3 = count_by_mod<ll>(lb, ub, 3, 0) - c15;
ll c1 = (ub - lb) - c3 - c5 - c15;
len += c15 * 8;
len += c5 * 4;
len += c3 * 4;
len += c1 * d;
if (len >= INFL) break;
}
return len;
};
//repi(i, 1, 16) dump(i, get_len(i));
//dump(11 * 16 + 0, get_len(11 * 16 + 0)); exit(0); // 176 552
auto okQ = [&](ll n) {
return get_len(n) <= Len;
};
auto n = meguru_search(0LL, INFL, okQ);
auto len = get_len(n);
//dump(n, len);
auto count_FB = [&](ll n) {
//dump("----------- n:", n, "-------------");
ll cnt = 0;
// d : 注目している桁
repi(d, 0, D - 1) {
ll c15B = count_arithmetic_mod<ll>(n / 15 + 1, pow16[d + 1], 15, 0, 11 * pow16[d], 12 * pow16[d]);
ll c5B = count_arithmetic_mod<ll>(n / 5 + 1, pow16[d + 1], 5, 0, 11 * pow16[d], 12 * pow16[d]) - c15B;
ll c3B = count_arithmetic_mod<ll>(n / 3 + 1, pow16[d + 1], 3, 0, 11 * pow16[d], 12 * pow16[d]) - c15B;
ll c1B = count_arithmetic_mod<ll>(n + 1, pow16[d + 1], 1, 0, 11 * pow16[d], 12 * pow16[d]) - c3B - c5B - c15B;
cnt += c1B;
//dump(d, "B", cnt);
ll c15F = count_arithmetic_mod<ll>(n / 15 + 1, pow16[d + 1], 15, 0, 15 * pow16[d], 16 * pow16[d]);
ll c5F = count_arithmetic_mod<ll>(n / 5 + 1, pow16[d + 1], 5, 0, 15 * pow16[d], 16 * pow16[d]) - c15F;
ll c3F = count_arithmetic_mod<ll>(n / 3 + 1, pow16[d + 1], 3, 0, 15 * pow16[d], 16 * pow16[d]) - c15F;
ll c1F = count_arithmetic_mod<ll>(n + 1, pow16[d + 1], 1, 0, 15 * pow16[d], 16 * pow16[d]) - c3F - c5F - c15F;
cnt += c1F;
//dump(d, "F", cnt);
}
//dump(cnt);
// 除原理
ll c15 = count_by_mod<ll>(1, n + 1, 15, 0);
ll c5 = count_by_mod<ll>(1, n + 1, 5, 0) - c15;
ll c3 = count_by_mod<ll>(1, n + 1, 3, 0) - c15;
cnt += c15 * 2;
cnt += c5 * 1;
cnt += c3 * 1;
//dump(cnt);
return cnt;
};
// repi(i, 1, 16) dump(i, count_FB(i));
ll res = count_FB(n);
auto ds = integer_digits(n + 1, 16);
if ((n + 1) % 15 == 0) ds = { 15, 0, 0, 0, 11, 0, 0, 0 };
else if ((n + 1) % 5 == 0) ds = { 11, 0, 0, 0 };
else if ((n + 1) % 3 == 0) ds = { 15, 0, 0, 0 };
rep(i, Len - len) {
if (ds[i] == 11 || ds[i] == 15) res++;
}
return res;
}
int main() {
// input_from_file("input.txt");
// output_to_file("output.txt");
//string s = "12Fizz4BuzzFizz78FizzBuzzBFizzDEFizzBuzz10";
//rep(i, sz(s)) dump(i + 1, s[i] == 'B' || s[i] == 'F');
//repi(i, 1, 50) dump(i, solve(i) - solve(i - 1)); return 0;
//dump(550, solve(550));
//dump(551, solve(551));
//dump(552, solve(552));
//return 0;
//
//repi(i, 769, 797) dump(i, solve(i) - solve(i - 1)); return 0;
ll L, R;
cin >> L >> R;
ll res = solve(R) - solve(L - 1);
EXIT(res);
}
/*
1 0
2 0
3 1
4 0
5 0
6 0
7 0
8 1
9 0
10 0
11 0
12 1
13 0
14 0
15 0
16 0
17 0
18 1
19 0
20 0
21 0
22 1
23 0
24 0
25 0
26 1
27 1
28 0
29 0
30 0
31 0
32 0
33 1
34 0
35 0
36 0
37 1
38 0
39 0
40 0
41 0
42 0
*/