题解：CF1909E Multiple Lamps

注意到有个 \lfloor \dfrac{n}{5} \rfloor，感觉很不好处理，但是还有一句话：“第 i 个开关控制了编号是 i 的倍数（包括 i）的所有灯”，你可以联想到小学数学的那道题，从 1 按到 n 只有平方数编号的灯亮着，因为他们的因数个数是奇数。解一下 \lfloor\sqrt{n}\rfloor \le \lfloor \dfrac{n}{5} \rfloor，发现 n \ge 25，但由于下取整其实是 n \ge 20。

那剩下的 n < 20 直接状压枚举一下不就行了。先不考虑限制预处理出所有按法，再对于每个询问在合法状态中找即可。

vector<int>ok[20];
inline void prework()
{
    for(int n{1};n<=19;n++)
    {
        for(int s{1};s<(1<<n);s++)
        {
            bitset<21>nowi(s);
            nowi<<=1;
            bitset<21>light;
            for(int i{1};i<=n;i++)
            {
                if(nowi[i])
                {
                    for(int j{i};j<=n;j+=i) light[j] = !light[j];
                }
            }
            if((int)light.count() > n/5) continue;
            ok[n].push_back(s);
        }
    }
}
inline void work()
{
    int n = read();
    if(n >= 20)
    {
        writeln(n);
        for(int i{1};i<=n;i++) writek(i);
        int m = read();
        while(m--) read(),read();
        return;
    }
    int m = read();
    vector<int>a(m+1),b(m+1);
    for(int i{1};i<=m;i++) a[i] = read(),b[i] = read();
    for(int s : ok[n])
    {
        bitset<25>nowi(s);
        nowi<<=1;
        bool tg = true;
        for(int i{1};i<=m;i++)
            if(nowi[a[i]] && !nowi[b[i]]) { tg = false;break;}
        if(!tg) continue;
        writeln(nowi.count());
        for(int i{1};i<=n;i++) 
            if(nowi[i]) writek(i);
        putchar(10);return;

    }
    puts("-1");
}