路灯问题

冬训期间,dalao提出了几个有关路灯的问题,觉得有趣就做了个记录.

问题1       

有 $n$ 盏路灯 $(n \leqslant 10^{18})$ ,初始状态为熄灭状态(下同).现输入 $k(k \leqslant 10^{8})$ 个数 $a_{i}(1\leqslant i\leqslant k, a_{i}\leqslant 10^{18})$ ,每个数代表对某盏路灯开关一次.最后哪盏灯是亮的?数据保证最后只有一盏是亮的状态.

例如,$1    2    1$意味着最后只有第 $2$ 盏灯是亮的.

问题2       

对问题$1$做出修改:若 $k(k \leqslant 10^{6})$ ,且数据保证最后有两盏灯是亮的状态,求对应的路灯编号.

问题3       

有 $n$ 盏路灯 $(n \leqslant 10^{8})$ ,每次对路灯的操作符合如下规律:

第 $i(1\leqslant i\leqslant n)$ 次对所有编号 $i$ 的倍数的路灯进行操作.求最后亮的所有路灯编号.


如果数据量比较小, 是很容易进行模拟求出答案的.但是显然这里不能直接模拟.事实上,不难看出,某盏灯亮一定是被进行了奇数次的操作.所以,问题 $1$ 被转化为输入数据中,求出现奇数次的数;问题 $2$ 则是求两个这样的数;问题 $3$ 是求这样的所有数,即它的所有因子个数为奇数.

我们首先考虑到,如果我们要统计所有数出现的次数,就意味着我们至少要有一个容器来存放这些数;从空间角度上来讲是不现实的.那么有没有一种比较简单的解决方案呢?实际上异或运算就可以很好地解决这个问题.

异或运算有这样的性质,它满足交换律和结合律;并且对任意数 $x$ ,有:

$x$^$0 = x$; $x$^$x = 0$

进而如果一个数出现偶数次,那么它们异或的结果必然为 $0$ ;把所有的数做异或运算,结果便是答案.

那么如果有两个数 $a_{m},a_{n} (a_{m} \neq a_{n})$ 出现偶数次呢?按照刚才的想法,最后的结果是这两个数的位或,即

$p = a_{m}$ ^ $a_{n}$

似乎无法将这两个数直接分开.

我们不妨考虑一下 $p$ 的特征:

首先,$p \neq 0 $ .因为条件限制一定有两个数出现了奇数次;所以如果将$p$用二进制表示,那么至少有第 $i$ 位是$1$.

考虑XOR的真值表,这一位的 $1$ 一定是 $0$ ^ $1 = 1$ 得来的.

因此$a_{m},a_{n}$满足这样的特征:

$ ((a_{m} >> i) $ & $1  =  1)$ && $((a_{n} >> i)$ & $1 = 0))$

这也就提示我们考虑将原来的所有数划分为两个集合,即二进制数第$i$位为$1$的数为一个集合,二进制数第 $i$ 位为 $0$ 的数为另一个集合;对这两个集合中的所有数进行XOR,最后得到两个结果就是答案.

#include <cstdio>
#include <cstdlib>
#include <iostream>

using namespace std;
using ll = long long;
const int maxn = 1e6+5;

ll pool[maxn]{0};

inline ll read()
{
    char ch=getchar();
    ll x=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return x*f;
}

inline ll check(ll x)
{
    return x & 1;
}

int main(void)
{
    ll k = read(),p = 0,x,j = 0;
    for(int i = 0;i < k;i++)
        pool[i] = read(),p ^= pool[i];
    while(!((p >>= 1) & 1))  j++;
    ll ans1 = 0,ans2 = 0;
    for(int i = 0; i < k;i++)
    {
        if(check(pool[i] >> j))
            ans1 ^= pool[i];
        else
            ans2 ^= pool[i];
    }
    printf("%lld %lld\n",ans1,ans2);
    return 0;
}

 

对于问题3,我们首先给出引理:

引理     完全平方数的因子个数为奇数.

引理的证明

我们熟知对于正整数 $n$ 有唯一素因子分解:

$n = p_{1}^{a_{1}}\cdot p_{2}^{a_{2}}\cdot…p_{s}^{a_{s}}$

那么其对应的因数个数为

$\tau(n) = \prod_{j = 1}^{s}\left ( a_{j} + 1 \right )$

由于 $n$ 是完全平方数,即 $a_{j} (1\leqslant j\leqslant s)$ 是偶数

所以 $\tau(n)$ 是奇数

所以这道题的答案就是 $1, 4, 9 … k^{2} $.


实际上,还有一个类似的关于因数个数的结论:

$\left [ 1,n \right ]$ 中含有因子 $ i $ 的个数之和为

$f(i) = \left \lfloor \frac{n}i \right \rfloor$


2019/1/20补充:

问题4

假设灯具有这样的性质:

第 $ 1 $次按下开关时颜色为黄色;第 $ 3 $次按下开关时颜色为绿色;

输入 $k(k \leqslant 10^{6})$  个数  $a_{i}(1\leqslant i\leqslant k, a_{i}\leqslant 10^{8})$最后结果只有 $ 1 $ 盏灯是黄色,求那盏灯的编号;数据保证每盏灯的操作次数只有 $ 1 $ 次或 $ 3 $ 次.

 

这里由于出现次数均为奇数,所以直接使用XOR是无效的;

实际上,如果某个元素出现了 $3$ 次,也就意味着如果将它用二进制表示,那么每一位的“  $ 1 $  ”出现了 $3$ 次;同理,出现  $1$ 次那个元素也就代表每一位的 ” $ 1$ “出现了 $ 1$ 次;

因此可以开一个长度为 $32$ (这里只考虑int32的简单情形) 的数组 $a_{n}$ 来记录 $1$ 出现次数.即:

$\left(ans >> i\ \&\ 1\ \right) = \begin{cases}
1 & \ \ \ a_{i}\equiv 1 \left ( mod \ 3 \right) \\
0 & \ \ \ a_{i}\equiv 0 \left ( mod \ 3 \right)
\end{cases}$

这样就可以构造出 $ans$.

vector<int> cnt(32,0);
vector<int>::iterator iter = nums.begin();
for(;iter != nums.end();iter++)
{
    for(int j = 0; j < 32;j++)
        if(((*iter) >> j) & 1)
            cnt[j]++;
}
int ans = 0;
for(int i = 31;i >= 0; i--)
    ans |= ((cnt[i] % 3 == 1) << i);
printf("%d\n",ans);

实际上,有一种更简单的方法解决这个问题.

int singleNumber(vector<int>& nums) 
{
    int ones = 0, twos = 0;
    for (int i = 0; i < nums.size(); i++) 
        {
        ones = (ones ^ nums[i]) & ~twos;
        twos = (twos ^ nums[i]) & ~ones;
    }
    return ones;
}

 

此条目发表在C++, 数论分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注