題目描述

小楊認為，所有大于等于 $a$ 的完全平方數都是他的超級幸運數。

小楊還認為，所有超級幸運數的倍數都是他的幸運數。自然地，小楊的所有超級幸運數也都是幸運數。

對于一個非幸運數，小楊規定，可以將它一直 $+1$，直到它變成一個幸運數。我們把這個過程叫做幸運化。例如，如果$a=4$，那么 $4$ 是最小的幸運數，而 $1$ 不是，但我們可以連續對 $1$ 做 $3$ 次 $+1$ 操作，使其變為 $4$，所以我們可以說， $1$幸運化后的結果是 $4$。

現在，小楊給出 $N$ 個數，請你首先判斷它們是不是幸運數；接著，對于非幸運數，請你將它們幸運化。

輸入格式

第一行 $2$ 個正整數 $a,N$。

接下來 $N$ 行，每行一個正整數 $x$ ，表示需要判斷（幸運化）的數。

輸出格式

輸出 $N$ 行，對于每個給定的 $x$ ，如果它是幸運數，請輸出 lucky，否則請輸出將其幸運化后的結果。

輸入輸出樣例 #1

輸入 #1

2 4 
1 
4 
5 
9

輸出 #1

4 
lucky 
8 
lucky

輸入輸出樣例 #2

輸入 #2

16 11 
1 
2 
4 
8 
16 
32 
64 
128 
256 
512
1024

輸出 #2

16 
16 
16 
16 
lucky 
lucky 
lucky 
lucky 
lucky 
lucky 
lucky

提交鏈接

平均分配

提示

樣例解釋 1

雖然是完全平方數，但它小于 $a$，因此它并不是超級幸運數，也不是幸運數。將其進行 $3$ 次 $+1$ 操作后，最終得到幸運數 $4$。4是幸運數，因此直接輸出 lucky 。

$5$ 不是幸運數，將其進行 $3$ 次 $+1$ 操作后，最終得到幸運數 $8$。

$9$ 是幸運數，因此直接輸出 lucky 。

數據規模

對于 $30\%$ 的測試點，保證 $a,x\le 100,N\le 100$。

對于 $60\%$ 的測試點，保證 $a,x\le 10^6$。

對于所有測試點，保證 $a\le 1,000,000$；保證 $N\le 2\times 10^5$；保證 $1\le x\le 1,000,001$。

解析

此題的關鍵，找出：

1. 找出所有超級幸運數：即大于等于 $a$ 的完全平方數；

2. 找出所有幸運數：所有超級幸運數及它們的倍數。

先考慮 $30\%$ 的數據。

此時的 $a$ 和 $x$ 的最大范圍為 $100$。我們可以暴力枚舉一定范圍，把這個范圍內的完全平方數全部找到。$a～1000$ 這個范圍一定是完全足夠。

用 $vis[]$ 來標記幸運數
枚舉完全平方數及其倍數

//判斷一個數 是否為完全平方數
bool check(int x)
{int ave = sqrt(x);return ave * ave == x;
}vector<int>ans;  //存儲 1e3 范圍內的幸運數字
//只考慮1e3的數據 看能過多少測試點
for(int i = a; i <= Mx; i++)
{if(check(i)){if(!vis[i]){ans.push_back(i);vis[i] = true;//考慮1e3范圍內的超級幸運數的倍數int rate = 2;while(rate * i <= Mx)  //考慮超級幸運數的倍數 {if(!vis[rate * i]){ans.push_back(rate * i);vis[rate * i] = true;}rate++;}}}
}

對于輸入的 $n$ 個數 $x$。若被標記則輸出lucky，否則我們可以根據二分找到第一個大于 $x$ 的位置輸出。

sort(ans.begin() , ans.end());  //從小到大排序
for(int i = 1; i <= n; i++)
{if(vis[x[i]])cout << "lucky" << endl;else{int pos = upper_bound(ans.begin() , ans.end() , x[i]) - ans.begin();cout << ans[pos] << endl;}}

對于 $100\%$ 的數據。
$a\le 1,000,000$、 $1\le x\le 1,000,001$。

最極端的情況，$x$ 為 $1000001$，$a$ 為 $1000000$，若沒有倍數的情況，大于 $a$ 的最小的完全平方數為 $1002001$。

我們可以借助 $30\%$ 數據的思路，對代碼進行優化，分析時間復雜度。

平方數從 $sqrt(a)$ 開始，最大的范圍到 $1002001(1001?1001=1002001)$

for (int i = ceil(sqrt(a)); i <= 1001; i++)

對于每一個完全平方數我們依然選出其倍數進行存儲。

// 能得出當x=1000001 最差的幸運數為1002001，1002001為完全平方數
for (int i = ceil(sqrt(a)); i <= 1001; i++)
{int x = i * i; // x為完全平方數for (int j = 1; j * x <= 1002001; j++){if (!vis[x * j])   //超級幸運數的倍數{ans.push_back(x * j);vis[x * j] = true;}}
}

此題的難點在于分析時間復雜度，考慮上述預處理代碼的時間復雜度：

遍歷從 $a$ 到 $up=1002001$：

• 如果 $i$ 是完全平方數，就遍歷它的所有倍數 $j=i,2i,3i,...,up$，時間為 $O(up/i)$；

一共操作的次數： $$\sum _{i^2\ge a}^{\sqrt{up}}\frac{up}{i^2}$$

化簡后，求和為一個收斂常數，時間復雜度大約為 $1e6$ 級別。

預處理后，對于每一個數 判斷標記 + 二分 進行輸出。

參考代碼

#include <bits/stdc++.h>
using namespace std;bool vis[1100000];int main()
{int a, n;cin >> a >> n;vector<int> ans; // 存儲幸運數字// 能得出當x=1000001 最差的幸運數為1002001，1002001為完全平方數for (int i = ceil(sqrt(a)); i <= 1001; i++){int x = i * i; // x為完全平方數for (int j = 1; j * x <= 1002001; j++){if (!vis[x * j])   //超級幸運數的倍數{ans.push_back(x * j);vis[x * j] = true;}}}sort(ans.begin() , ans.end());while (n--){int x;cin >> x;if (vis[x])cout << "lucky" << endl;else{int pos = upper_bound(ans.begin(), ans.end(), x) - ans.begin();cout << ans[pos] << endl;}}return 0;
}