結果
| 問題 |
No.3136 F,B in FizzBuzzString16
|
| ユーザー |
 ripity
|
| 提出日時 | 2025-05-03 00:17:58 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 18,433 bytes |
| コンパイル時間 | 3,605 ms |
| コンパイル使用メモリ | 285,964 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-03 00:18:31 |
| 合計ジャッジ時間 | 32,736 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 7 |
| other | AC * 26 TLE * 6 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const vector<ll> VEC_LEN = {1163788961, 1243501087, 1280000000, 1280000004, 1279999996, 1280000000, 1280000004, 1279999996, 1280000000, 1280000004, 1279999996, 1280000000, 1280000004, 1279999996, 1280000000, 1280000004, 1279999996, 1280000000, 1280000004, 1279999996, 1280000000, 1336017447, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1386666662, 1386666667, 1386666671, 1429612403, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334, 1493333338, 1493333328, 1493333334};
const vector<ll> VEC_VAL = {194410158, 196401355, 204670361, 201247199, 194976768, 199258042, 204670363, 198975420, 194977858, 202087971, 204670361, 196145222, 194977862, 204358925, 229849016, 302218931, 206581826, 204668174, 204649339, 195679093, 288231220, 255317538, 204635410, 195687694, 195720606, 204168738, 204575333, 195687563, 195336393, 204494644, 204633773, 195687696, 195722513, 204659984, 204624758, 195704218, 276918616, 266560781, 204116035, 195722653, 195722514, 245941108, 305931675, 195722514, 195722513, 204633362, 204633225, 195722649, 195722513, 204629400, 204053233, 194747666, 196692717, 204450134, 201164459, 195015133, 199517046, 235180649, 305383083, 200966210, 202347113, 204634998, 195886351, 292897796, 249898940, 204635406, 195292982, 195572053, 204626943, 204660397, 195720325, 195685513, 204635412, 204670360, 195720328, 195601273, 204160271, 204670497, 195720331, 281690590, 261236666, 204670362, 195716780, 195676908, 251882773, 300600727, 195685375, 195685516, 204336399, 204445080, 195686196, 195466104, 204329575, 204670500, 195687284, 195685786, 204668179, 204670360, 195687562, 195685376, 240583270, 310169531, 195555399, 197009884, 204198774, 201131692, 298232832, 239754513, 204668178, 198391602, 194980043, 202671926, 204668177, 195561403, 195254478, 204668175, 204644693, 195131735, 195707767, 204668312, 204633500, 195687287, 287655047, 255902312, 204633499, 195686329, 195346504, 257090831, 295195235, 195423782, 195424868, 204670362, 204625854, 195692884, 195722512, 204637731, 204631039, 195720326, 195722518, 204076167, 204633223, 195720469, 195211057, 245871068, 306515493, 195720328, 195722514, 204635409, 206587562, 302387133, 230247150, 204458870, 203395141, 195013089, 197216457, 204129962, 200963756, 195013221, 200099225, 204635547, 198134511, 195012809, 202928747, 204635408, 195304447, 292872945, 250489581, 204347460, 195466925, 195685376, 262605004, 289864158, 195722513, 195685514, 204633224, 204670496, 195722511, 195126140, 204633225, 204670358, 195169009, 195677047, 204635953, 204670501, 195694387, 195679093, 251319984, 301183588, 195687561, 195476891, 204319468, 211991143, 302258383, 224400520, 204668176, 204668176, 195687559, 195687700, 204668178, 204653019, 195679094, 195711320, 204208061, 203366464, 194980049, 197252095, 204454638, 200635668, 297649013, 240924330, 204668178, 197805465, 194980045, 266597924, 284488839, 195120263, 195698484, 204670363, 204074801, 195685650, 195721421, 204670497, 204635140, 195685781, 195720328, 204670364, 204635411, 195433058, 195413403, 256690246, 295643337, 195264173, 195720327, 204646879, 217317718, 302383990, 302386995, 311302215, 311302073, 302387128, 301884833, 311245002, 311302075, 301999242, 302215509, 311302213, 311302077, 302387129, 302376619, 311293340, 312691712, 409054753, 337436196, 310786114, 309877486, 301681805, 372668070, 353547947, 200380760, 195014995, 200682496, 204633363, 197550693, 195015132, 203506284, 204345137, 195457638, 195690836, 204449997, 204289026, 195722513, 195687696, 262021186, 290445792, 195722514, 195687559, 204633224, 222727305, 301844957, 214112599, 204633497, 204238641, 195573695, 195679094, 204661896, 204668590, 195685921, 195687693, 204670366, 204668177, 195598814, 195214881, 204670361, 211407055, 301792801, 225447867, 204670358, 204662174, 195676911, 269778464, 273759508, 204633357, 195685376, 195386235, 204447539, 202881771, 194755862, 197844237, 204670363, 200051852, 194977856, 201011678, 204670362, 197220559, 194979771, 266596966, 284493480, 195679233, 195720604, 204196725, 227975236, 302354228, 302386995, 311334843, 311302079, 302354361, 302386994, 311334982, 311173464, 301923598, 302386996, 311306445, 310748570, 302377030, 302386992, 311300028, 323409034, 409055847, 326778948, 311299891, 311302075, 302010844, 381650880, 332075210, 204371352, 195427330, 195719781, 204625033, 204644148, 195722649, 195687285, 204633637, 204668178, 195722511, 195128321, 204633223, 202624819, 194501226, 266517500, 279674539, 199794760, 195014994, 201268497, 233428652, 303631359, 202696227, 203919432, 204275641, 195720327, 195631310, 204132420, 204668178, 195720327, 195687698, 204635407, 204668316, 195720601, 195687284, 204635412, 221723920, 302238994, 214701605, 204347321, 204417363, 195685379, 280498243, 263023072, 204670362, 195685376, 195685511, 204670362, 204670500, 195126133, 195685376, 204670363, 204114397, 195676912, 195690699, 204670359, 204639920, 195681005, 269212943, 274343325, 204635406, 195259941, 195586663, 238834005, 308868640, 196852466, 198763382, 204669815, 199470083, 194979222, 201593583, 204650976, 196631688, 195006257, 203960661, 204536559, 195687561, 195374355, 204457230, 227476615, 302354368, 209378028, 204668175, 204633230, 195687559, 285903598, 257642976, 204070432, 195701078, 195722513, 204073985, 204633225, 195722513, 195722511, 204633361, 204633225, 195722651, 195722512, 204633771, 204378726, 195417223, 274583351, 268798837, 204215160, 195720741, 195696570, 244158803, 308301347, 195720331, 195687557, 204635548, 204668178, 194711209, 196137575, 204635406, 201650792, 194843787, 199022248, 204635546, 199210942, 194999839, 201843848, 232868593, 303047544, 203265159, 204123139, 204670495, 195720328, 290675579, 252251680, 204670360, 195721150, 195685650, 204634314, 204670499, 195721966, 195677321, 204345142, 204407942, 195688381, 195502149, 204291343, 204670498, 195687562, 279914564, 263604701, 204670361, 195687564, 195685372, 249568258, 302389316, 195674999, 195685515, 204235910, 204522083, 195679099, 195715141, 204668175, 204635548, 195687558, 195720465, 204668453, 204457093, 194509826, 196517958, 238248276, 307822522, 197899132, 199349246, 204659709, 198875618, 295914495, 244427230, 204633223, 196054153, 195014996, 204450137, 204633223, 195460912, 195387739, 204670358, 204633224, 195685514, 195722512, 204670499, 204629131, 195689470, 285319782, 257649937, 204627763, 195720465, 195248198, 254818918, 297530774, 195720604, 195721965, 204635410, 204634590, 195720736, 195720877, 204504474, 204207239, 195720324, 195687022, 204084359, 204660531, 195720466, 195685375, 243583589, 308887894, 195720330, 195685374, 204635411, 203908505, 301120377, 233653656, 204369031, 201166642, 195008993, 199595417, 204647696, 198629309, 194977994, 202433945, 204670502, 195799245, 195049945, 204633503, 204669541, 195206143, 290609769, 252833585, 204668586, 195722515, 195687561, 260269737, 311334845, 302364328, 302172777, 310947091, 311334976, 302295519, 301853697, 311334844, 311334843, 302354229, 302354362, 311334843, 311334983, 302354227, 302354224, 355228130, 410035882, 302345762, 302066280, 311084164, 316287319, 409020896, 258745751, 204668996, 204633498, 195686467, 195722650, 204670091, 203401553, 194977861, 197102866, 204111942, 201121858, 194985507, 199933065, 204637316, 198298493, 295346516, 245594860, 204635409, 195470200, 195376264, 265675234, 286695490, 195227031, 195720333, 204670360, 204635409, 195685376, 195720329, 204650292, 204626946, 195714183, 195255567, 204540930, 204635409, 195370802, 195511981, 254318658, 298116502, 195722654, 195720326, 204633225, 214990917, 302389178, 221848989, 204073029, 204651244, 195722647, 195126141, 204633223, 204670362, 195722513, 195685375, 204633361, 204670362, 195722651, 195685373, 204375998, 203403605, 300716919, 234675475, 204219935, 200875554, 194986738, 266554367, 311335116, 304711613, 301646710, 309685794, 311335257, 301880454, 302302205, 311302082, 310942172, 302220422, 302354229, 311302075, 311334981, 302371432, 302345896, 366378803, 399447723, 302302616, 301844412, 311337032, 327058701, 408459468, 237238069, 204670363, 204668175, 195685377, 195687560, 204670361, 204665587, 195676908, 195399610};
const ll L = 1'000'000'000'000LL;
const ll B = 2'000'000'00LL;
ll g(ll l, ll r, ll k) {
ll len = 0;
ll sum = 0;
// cout << l << " " << r << endl;
for(ll x = l; x < r && len < k; x++) {
if(x == 0) {
continue;
}else if(x % 15 == 0) {
if(len + 8 >= k) {
ll rem = k - len;
sum += (rem >= 1);
sum += (rem >= 5);
break;
}
len += 8;
sum += 2;
}else if(x % 5 == 0) {
if(len + 4 >= k) {
ll rem = k - len;
sum += (rem >= 1);
break;
}
len += 4;
sum += 1;
}else if(x % 3 == 0) {
if(len + 4 >= k) {
ll rem = k - len;
sum += (rem >= 1);
break;
}
len += 4;
sum += 1;
}else {
ll y = x;
vector<int> D;
if(k - len <= 15) {
while(y) {
D.push_back(y & 15);
y = y >> 4;
}
reverse(D.begin(), D.end());
for(int d : D) {
if(len >= k) break;
len += 1;
sum += (d == 15 || d == 11);
}
}else {
int d;
while(y && len < k) {
d = y & 15;
y = y >> 4;
len += 1;
sum += (d == 15 || d == 11);
}
}
}
// cout << x << " : " << len << " " << sum << endl;
}
return sum;
}
ll f(ll x) {
ll ret = 0;
for(ll i = 0; i < L; i += B) {
if(x >= VEC_LEN[i / B]) {
ret += VEC_VAL[i / B];
x -= VEC_LEN[i / B];
}else {
// cout << i << endl;
ret += g(i, i + B, x);
break;
}
}
return ret;
}
std::string to_hex_string(int64_t i) {
std::stringstream s;
s << std::uppercase << std::hex << i;
return s.str();
}
std::string FizzBuzz16(int64_t i) {
if (i % 15 == 0) {
return "FizzBuzz";
} else if (i % 3 == 0) {
return "Fizz";
} else if (i % 5 == 0) {
return "Buzz";
} else {
return to_hex_string(i);
}
}
std::string FizzBuzzString16(int64_t n) {
std::string s = "";
for (int64_t i = 1; i <= n; i++) {
s += FizzBuzz16(i);
}
return s;
}
int main() {
ll X, Y;
cin >> X >> Y;
cout << f(Y) - f(X - 1) << endl;
// cout << FizzBuzzString16(50) << endl;
// for(ll x = X; x <= Y; x++) {
// ll v = f(x) - f(x - 1);
// cout << v;
// }
// cout << endl;
}