題目描述

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

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

輸出格式
輸出開燈的編號。

輸入樣例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

思路解析：

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

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

int main(void)

{

? ? int k;

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

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

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

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

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

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

}

留言：

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