제출 #856457

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
856457		Tenis0206	Present (RMI21_present)	C++11	29 / 100	4059 ms	596 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int vmax = 40;
const int bsize = 1e6;

long long prec[] = {0, 33751120, 75992704, 116437760, 170614864, 230739856, 290855208, 354085568, 432244832, 531108448, 568870688, 612293120, 651920640, 705855104, 765146688, 826166528, 889429120, 965887808, 1063268928, 1145670528, 1233666336, 1357252096, 1505104128, 1644323088, 1726914048, 1843922208, 1973754368, 2150009872, 2185705088, 2227254408, 2272958016, 2325220800, 2386308240, 2447666208, 2512312576, 2591771712, 2686090016, 2721489216, 2762873488, 2807207488, 2860812368, 2921068096, 2982805896, 3046299200, 3125530176, 3223828512, 3299634704, 3397945616, 3523766536, 3685626112, 3802412048, 3892963728, 4007963664, 4140022912, 4301802760, 4353034880, 4402669624, 4468565696, 4543038392, 4623235264, 4703717768, 4812658880, 4870252424, 4918602832, 4979177568, 5051793568, 5131293864, 5208637760, 5311823912, 5417085520, 5531666560, 5687198016, 5905123840, 5994130584, 6130049584, 6292111496, 6454259872, 6511693920, 6557657280, 6627134064, 6711354536, 6783327528, 6864351264, 6981069440, 7025420608, 7080077784, 7139986624, 7216432208, 7290677440, 7371380352, 7479902368, 7587832368, 7711779344, 7862047392, 8061938968, 8162263632, 8306524800, 8474812960, 8619458944, 8685561344, 8760789184, 8850582080, 8948023424, 9071651072, 9161177344, 9228085952, 9303638624, 9395527744, 9492504832, 9615980800, 9744052736, 9895085184, 10114290176, 10281165440, 10433341056, 10653118464, 10775450880, 10842555328, 10919442176, 11009632256, 11110679040, 11237118592, 11316925952, 11384145984, 11462682368, 11551709952, 11653816576, 11782643840, 11908956416, 12069507328, 12295696896, 12446851616, 12608136448, 12833415424, 12952498432, 13032334976, 13145565760, 13265348864, 13423661568, 13499446400, 13593226496, 13701644544, 13834099200, 13993033984, 14170210560, 14437379328, 14630293760, 14842274048, 15057807424, 15141962560, 15242871360, 15364703232, 15504894720, 15611934784, 15704042176, 15804195968, 15919571200, 16073691392, 16240765056, 16452624896, 16710233728, 16884933760, 17176858624, 17215603728, 17258585152, 17303254144, 17360424320, 17422199936, 17486410016, 17551613984, 17639549952, 17722977440, 17763029136, 17804493888, 17855263872, 17918593552, 17977889920, 18041336960, 18106585600, 18198168640, 18284288416, 18367884928, 18485833856, 18615394592, 18795470496, 18872432128, 18979530880, 19104194816, 19268671616, 19350923296, 19399050160, 19437364032, 19491981632, 19553126528, 19614720576, 19680465184, 19760055936, 19861793408, 19899620096, 19942681120, 19987061824, 20044608320, 20106082400, 20170567424, 20235504128, 20323087488, 20412543360, 20493638528, 20607293088, 20737611008, 20900760192, 21007125120, 21091191584, 21218992544, 21358907520, 21489286176, 21548104960, 21602797120, 21679057056, 21752232256, 21825864256, 21925470600, 22021377664, 22080210208, 22125879696, 22200562816, 22281659680, 22356124960, 22448013952, 22557785728, 22658409488, 22807219328, 22975048192, 23137194496, 23253420352, 23412868608, 23622733264, 23667688704, 23723083584, 23786463904, 23862815872, 23939034368, 24026577216, 24135755520, 24197661280, 24247788672, 24308195488, 24387400256, 24466080136, 24542864832, 24655072256, 24765866912, 24880732672, 25040142496, 25239984256, 25338696960, 25480963392, 25648845440, 25801410336, 25870863008, 25950302752, 26042672768, 26147844928, 26280617216, 26359292480, 26429272192, 26516541760, 26609197280, 26720422464, 26854607648, 26988500480, 27175522816, 27394319008, 27529323936, 27718001280, 27926620064, 27994676480, 28068036928, 28155452032, 28261305728, 28387309184, 28481882144, 28550907168, 28631285824, 28723988800, 28826709248, 28958476352, 29086202912, 29247800448, 29474644288, 29628945664, 29796393120, 30021968384, 30135226688, 30224783424, 30339126080, 30471963968, 30612794528, 30702350976, 30806055040, 30921015872, 31072465216, 31222825504, 31422039296, 31691469056, 31877409184, 32122657280, 32274014752, 32358038080, 32474053760, 32598559232, 32754349312, 32834130496, 32938508864, 33053451520, 33194456704, 33358300448, 33548929152, 33827611296, 33993340160, 34234159744, 34402271560, 34478852672, 34582462480, 34707458112, 34874652736, 34962510336, 35040668880, 35148836368, 35279373888, 35455317632, 35635387904, 35933571328, 36111656976, 36366641408, 36550183568, 36627939904, 36731348032, 36855955528, 37023918344, 37111359848, 37189024544, 37298028816, 37428101696, 37606161920, 37784922896, 38086380560, 38261129732, 38518737408, 38710684808, 38816918020, 38960687680, 39143580736, 39263897744, 39372219400, 39524068424, 39719609408, 39938236560, 40287631360, 40520102912, 40822901248, 40917855504, 41050403392, 41214339648, 41377300624, 41477198400, 41613658632, 41784813572, 41989319752, 42304640000, 42565330944, 42924147264, 43059326032, 43208353296, 43425997840, 43572662352, 43716221504, 43917734976, 44168294404, 44569395344, 44848924928, 45149203776, 45282271764, 45464966400, 45668224016, 45794132176, 45966492736, 46205374224, 46506576912, 46850673680, 47247084816, 47399937168, 47621169728, 47850033792, 48024954000, 48289669696, 48651641344, 49066617152, 49444061376, 49619600400, 49873373216, 50050386432, 50257933888, 50545599632, 51007561872, 51384451648, 51596235072, 51678664256, 51788581896, 51921870856, 52086072832, 52163215888, 52258906432, 52380885312, 52531704384, 52702421128, 52924128000, 53200967704, 53396277520, 53692999376, 53768459584, 53863457544, 53981362440, 54130617408, 54261903680, 54338366848, 54445736512, 54572941640, 54744785984, 54909350528, 55172541456, 55404840208, 55639394560, 55874078728, 55975813712, 56116339976, 56305635904, 56439489864, 56547708048, 56697473536, 56896889920, 57116480768, 57466162184, 57696982144, 58004025480, 58101623312, 58242279568, 58414602272, 58565757336, 58669302848, 58821340928, 59005055552, 59222186496, 59576011264, 59802769664, 60141950208, 60272834848, 60443279936, 60675305104, 60803291728, 60971737664, 61212489744, 61500868864, 61860759808, 62256709952, 62394078784, 62555272448, 62790282304, 62924798592, 63084570912, 63316173376, 63586260224, 63965683200, 64309577984, 64541349120, 64760769088, 65004898112, 65180419088, 65442730560, 65786268160, 66215683728, 66616062528, 66792428608, 67054474016, 67240961152, 67454373440, 67755254032, 68216889488, 68623307008, 68763799056, 68829854592, 68958882216, 69056540072, 69164750944, 69283351848, 69346248896, 69459326048, 69563958464, 69657027136, 69829104256, 70066199944, 70340192648, 70542700688, 70837896320, 70916968768, 70982862992, 71118498112, 71208627656, 71338284160, 71439075648, 71504939840, 71615172928, 71718740296, 71815873800, 71992000896, 72225210912, 72500117640, 72727005312, 73016228936, 73090357256, 73217673224, 73330359936, 73451617408, 73587794752, 73665898632, 73826520864, 73919049248, 74094282888, 74369411464, 74671283840, 74964995872, 75195166368, 75272718144, 75434826120, 75515481664, 75698942408, 75771964168, 75882540352, 76010927424, 76116151584, 76322678816, 76619881728, 76920985888, 77267627040, 77391992336, 77569991824};

int my_gcd[vmax + 5][vmax + 5];

struct sir
{
    vector<int> st;
    bool fr[vmax + 5];
    int Max;
    sir()
    {
        Max = 0;
        memset(fr,false,sizeof(fr));
    }
};

sir get_next(sir s)
{
    for(int val=1;val<=s.Max+1;val++)
    {
        if((s.st.empty() || s.st.back()!=val) && !s.fr[val])
        {
            s.st.push_back(val);
            break;
        }
        if(!s.st.empty() && s.st.back()==val)
        {
            s.st.pop_back();
        }
    }
    sir rez;
    rez.st = s.st;
    if(rez.st.size())
    {
        rez.Max = rez.st.front();
    }
    for(auto it : rez.st)
    {
        rez.fr[it] = true;
    }
    for(int a=rez.Max;a>=1;a--)
    {
        for(int b=a-1;b>=1;b--)
        {
            if(!rez.fr[a] || !rez.fr[b])
            {
                continue;
            }
            rez.fr[__gcd(a,b)] = true;
        }
    }
    return rez;
}

sir conv_mask(long long val)
{
    sir rez;
    int k = 0;
    for(int b=vmax;b>=1;b--)
    {
        if((val & (1LL<<b)) != 0)
        {
            if(!rez.Max)
            {
                rez.Max = b;
            }
            rez.st.push_back(b);
        }
    }
    for(int a=vmax;a>=1;a--)
    {
        for(int b=a-1;b>=1;b--)
        {
            if(!(val & (1LL<<a)) || !(val & (1LL<<b)) )
            {
                continue;
            }
            val |= (1LL<<my_gcd[a][b]);
        }
    }
    for(int b=1;b<=vmax;b++)
    {
        if((val & (1LL<<b)) != 0)
        {
            rez.fr[b] = true;
        }
    }
    return rez;
}

void solve_test()
{
    int k;
    cin>>k;
    int start = (k / bsize) * bsize;
    sir rez = conv_mask(prec[k / bsize]);
    for(int i=start+1;i<=k;i++)
    {
        rez = get_next(rez);
    }
    vector<int> r;
    for(int val=1;val<=vmax;val++)
    {
        if(rez.fr[val])
        {
            r.push_back(val);
        }
    }
    cout<<r.size()<<' ';
    for(auto it : r)
    {
        cout<<it<<' ';
    }
    cout<<'\n';
}

int main()
{
    #ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    #endif // home
    for(int i=1; i<=vmax; i++)
    {
        for(int j=1; j<=vmax; j++)
        {
            my_gcd[i][j] = __gcd(i,j);
        }
    }
    int t;
    cin>>t;
    for(int test=1;test<=t;test++)
    {
        solve_test();
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'sir conv_mask(long long int)':
Main.cpp:65:9: warning: unused variable 'k' [-Wunused-variable]
   65 |     int k = 0;
      |         ^

• Subtask 1: 8 / 8
• Subtask 2: 21 / 21
• Subtask 3: 0 / 41
• Subtask 4: 0 / 14
• Subtask 5: 0 / 16