題目描述

有 n 盞燈，編號(hào)為 1~n，第 1 個(gè)人把所有燈打開(kāi)，第 2 個(gè)人按下所有編號(hào)為 2 的倍數(shù)的開(kāi)關(guān)（這些燈將被關(guān)掉），第 3 個(gè)人按下所有編號(hào)為 3 的倍數(shù)的開(kāi)關(guān)（其中關(guān)掉的燈將被打開(kāi)，開(kāi)著的燈將被關(guān)閉），依此類推。一共有 k 個(gè)人，問(wèn)最后有哪些燈開(kāi)著？輸入：n 和 k，輸出開(kāi)著的燈編號(hào)。k ≤ n ≤ 1000。

輸入格式
輸入一組數(shù)據(jù)：n 和 k，中間空格隔開(kāi)。

輸出格式
輸出開(kāi)燈的編號(hào)。

輸入樣例1
輸入
4 3
輸出
1
輸入樣例2
輸入
7 3
輸出
1
5
6
7
輸入樣例3
輸入
10 6
輸出
1
4
7
8
10
輸入樣例4
輸入
15 1
輸出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
輸入樣例5
輸入
21 5
輸出
1
4
6
7
8
10
11
13
15
16
17
18
19

思路解析：

????????在開(kāi)始之前我要介紹一個(gè)運(yùn)算符符號(hào)“^”，這個(gè)運(yùn)算符號(hào)在C語(yǔ)言中表達(dá)的含義是異或，兩個(gè)數(shù)字都為1或者0，異或值為0，一個(gè)為1另一個(gè)為0，異或值則為1。

? ? ? ? 為了方便大家理解，可以將開(kāi)燈關(guān)燈的過(guò)程也包含在代碼中（雖然運(yùn)行會(huì)比較慢），我們可以定義一個(gè)一維數(shù)組表示一排燈，下標(biāo)則為對(duì)應(yīng)燈的編號(hào)。數(shù)組值1，0表示燈的狀態(tài)分別是開(kāi)燈和關(guān)燈，編寫(xiě)一個(gè)函數(shù)，模擬開(kāi)燈關(guān)燈。

具體代碼：

#include<stdio.h>

int arr[100] = {0};

int n;

void fun(int k)

{

? ? for(int i = k;i<=n;i+=k)

? ? ? ? arr[i] = 1^arr[i];//1變0，0變1

}//模擬第k個(gè)人開(kāi)燈關(guān)燈操作。

int main(void)

{

? ? int k;

? ? scanf("%d%d",&n,&k);

? ? for(int i = 1;i<=k;i++)

? ? ? ? fun(i);//讓k個(gè)人輪流執(zhí)行開(kāi)燈關(guān)燈操作。

? ? for(int i = 1;i<=n;i++)

? ? ? ? if(arr[i])//如果還有燈為開(kāi)的狀態(tài)，打印該編號(hào)。

? ? ? ? ? ? printf("%d\n",i);

}

留言：

? ? ? ? 基礎(chǔ)題也講過(guò)不少了，之后我打算開(kāi)啟圖論的內(nèi)容，會(huì)比較難，不過(guò)當(dāng)然還是從最簡(jiǎn)單的開(kāi)始，修行在當(dāng)下，諸君切莫急。