编程求解<闪烁灯泡>

Question

C++编程求解

描述
马上就要迎来新年了，小A为了装饰自己的房间，决定在新年那一天挂起彩灯，已知彩灯每隔一分钟就会闪烁一下，闪烁的规律如下：
第一次只亮第1只灯
第二次只亮第3只灯
第三次只亮第6只灯
第四次只亮第10只灯，以此类推…
注意：彩灯是环状的，也就是说，如果只有5只灯泡，那么第6只就是第1只。
请问经过x分钟之后有哪些灯没有亮过，如果所有灯都亮过，请计算亮的次数最多灯泡是几号。

输入
一行，两个整数，分别表示灯泡的个数m（1≤ m ≤1000）m（1≤m≤1000）和经过的分钟n（1≤ n ≤10000）n（1≤n≤10000）

输出
如果有灯泡没亮，那么输出所有没有亮过的灯泡编号；如果所有灯泡都亮过，那么输出亮的次数最多的灯泡编号（如果存在多个灯泡，输出编号最小的那只）。

输入样例 1

10 4

输出样例1

2 4 5 7 8 9

Answer 1

观察亮灯的规律，如下：

原数组：1 3 6 10
作 差： 1 2 3 4

发现原数组的差分数组是等差数列。

直接模拟即可，时间复杂度 O(n) .

#include <bits/stdc++.h>
using namespace std;
int n, m, vis[10005];// vis[i] 记录第 i 盏灯亮了多少次
int main() {
    scanf("%d%d", &m, &n);
    for (int i = 1, d = 1, now = 1; i <= n; i++, d++, now += d) {// d 是差值，也就是说下一次 now 要加上 d，now 是当前的位置
        if (now > m) now -= m;// now 超过了 m，要回去
        vis[now]++;//统计第 now 盏灯出现的次数
    }
    int fl = 0, mx = 0;
    for (int i = 1; i <= m; i++)
        if (!vis[i]) fl = 1;//第 i 盏灯没有亮过
        else if (vis[mx] < vis[i]) mx = i;//求出现次数最多的灯
    if (!fl) printf("%d", mx);//所有灯都亮过了
    else//有灯没亮过
        for (int i = 1; i <= m; i++)
            if (!vis[i])
                printf("%d ", i);
    return 0;
}