# include <bits/stdc++.h>
# define int long long
using namespace std;
int n, p = INT_MIN;
bool prime(int x)
{
if (x < 2) return 0;
if (x == 2) return 1;
for (int i = 2; i * i <= x; i++) if (x % i == 0) return 0;
return 1;
}
signed main()
{
cin >> n;
for (int i = 1; i <= n; i++)
if (n % i == 0 && prime(i)) p = i;
cout << p;
return 0;
}
此题……分外的水啊……
我直接写上质数暴力判断，然后一个个因数检查至最大
但我还是 WA 了……
查了查，TLE 了 4 个点
一个个输入及其的大，O(n) 的时间复杂度根本吃不消
结果看题时猛然发现……
已知正整数 n 是两个不同的质数的乘积
那还判个啥，输出就完了
修改后
# include <bits/stdc++.h>
# define int long long
using namespace std;
int n, p = INT_MIN;
bool prime(int x)
{
if (x < 2) return 0;
if (x == 2) return 1;
for (int i = 2; i * i <= x; i++) if (x % i == 0) return 0;
return 1;
}
signed main()
{
cin >> n;
for (int i = 1; i <= n; i++)
if (n % i == 0 && prime(i))
{
cout << p;
break;
}
return 0;
}
但我再仔细一看，我又发现，还能再优化：
因为 n 一定是两个质数的乘积
所以只要从 2 判断到 \sqrt{n} 即可
优化后
# include <bits/stdc++.h>
using namespace std;
int n;
int main()
{
cin >> n;
for (int i = 2; i <= sqrt(n); i++)
if (n % i == 0)
{
cout << n / i;
break;
}
return 0;
}
说明书的内容如下：藏宝楼共有 N+1 层，最上面一层是顶层，顶层有一个房间里面藏着宝藏。除了顶层外，藏宝楼另有 N 层，每层 M 个房间，这 M 个房间围成一圈并按逆时针方向依次编号为 0，…，M-1。其中一些房间有通往上一层的楼梯，每层楼的楼梯设计可能不同。每个房间里有一个指示牌，指示牌上有一个数字 x，表示从这个房间开始按逆时针方向选择第 x 个有楼梯的房间（假定该房间的编号为 k），从该房间上楼，上楼后到达上一层的 k 号房间。比如当前房间的指示牌上写着 2，则按逆时针方向开始尝试，找到第 2 个有楼梯的房间，从该房间上楼。如果当前房间本身就有楼梯通向上层，该房间作为第一个有楼梯的房间。
$1$号房间，无楼梯通往上层，指示牌上的数字是$3$；
$2$号房间，有楼梯通往上层，指示牌上的数字是$4$；
第二层：
$0$号房间，无楼梯通往上层，指示牌上的数字是$1$；
$1$号房间，有楼梯通往上层，指示牌上的数字是$5$；
$2$号房间，有楼梯通往上层，指示牌上的数字是$2$；
小明首先进入第一层（底层）的 $1$ 号房间，记下指示牌上的数字为 $3$，然后从这个房间开始，沿逆时针方向选择第 $3$ 个有楼梯的房间$2$号房间进入，上楼后到达第二层的 $2$ 号房间，记下指示牌上的数字为 $2$，由于当前房间本身有楼梯通向上层，该房间作为第一个有楼梯的房间。因此，此时沿逆时针方向选择第 $2$ 个有楼梯的房间即为 $1$ 号房间，进入后上楼梯到达顶层。这时把上述记下的指示牌上的数字加起来，即 $3+2=5$，所以打开宝箱的密钥就是 $5$。
【数据范围】
对于 $50\%$ 数据，有 $0<N\leqslant1000$，$0<x\leqslant10000$；
对于 $100\%$ 数据，有 $0<N\leqslant10000$，$0<M\leqslant100$，$0<x\leqslant1,000,000$。
## 原代码
```cpp
# include <bits/stdc++.h>
# define int long long
using namespace std;
int n, m, start, cnt, k, ans, mp[10005][105];
bool bol[10005][105];
signed main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 0; j < m; j++)
cin >> bol[i][j] >> mp[i][j];
cin >> start;
cout << endl;
k = start;
for (int i = 1; i <= n; i++)
{
ans += mp[i][start];
while (cnt <= mp[i][start])
{
if (k == m) k = 0;
if (bol[i][k]) cnt++;
cout << cnt << endl;
if (cnt < mp[i][start]) k++;
}
start = k;
cnt = 0;
}
cout << ans;
return 0;
}
```
提交后我发现了一个令人脑抽的问题：我**测试代码没删，而且没有模……**
整体思路也算简单，一个数组 $bol_{i,j}$ **储存此房间是否有楼梯**，另一个数组 $mp_{i,j}$ **储存地图中的指示牌**
接着就是约瑟夫大模拟：用 $start$ **储存指示牌位置**，$k$ **储存小明的位置**，$ans$ **储存指示牌之和**，$cnt$ **储存上楼次数**，按照题意进行模拟
于是我修改了一下再提交，信心满满的我……
## 修改后
```cpp
# include <bits/stdc++.h>
# define int long long
using namespace std;
int n, m, start, k, ans, mp[10005][105];
bool bol[10005][105];
signed main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 0; j < m; j++)
cin >> bol[i][j] >> mp[i][j];
cin >> start;
k = start;
for (int i = 1; i <= n; i++)
{
ans += mp[i][start];
ans %= 20123;
while (mp[i][start] > 0)
{
k++;
k %= m;
if (bol[i][k]) mp[i][start]--;
}
start = k;
}
cout << ans;
return 0;
}
```
大大的 **WA + TLE** 写在测试点上
我仔细观察了一下，发现了一些问题：
1. **若 $mp_{i,start} = 0$，则直接上楼**，而我**没有特判**
2. 修改后的代码，**不会判断起始点有没有楼梯**
## 最后一个是最致命的 bug：
**如果 $x$ 特别大，如每层都是 999999，我们的程序就要执行整整 99999900 次，这对 1 秒的时限是十分致命的！**
所以我们可以解决一下这个问题（另两个不做太多解释）
我们重新创建一个 $cnt_i$，储存**每层的楼梯数**，然后将 $mp_{i,start}$ **取模**，**节省大量时间**
## 新代码
```cpp
# include <bits/stdc++.h>
# define int long long
using namespace std;
int n, m, start, cnt[10005], k, ans, mp[10005][105];
bool bol[10005][105];
signed main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 0; j < m; j++)
{
cin >> bol[i][j] >> mp[i][j];
if (bol[i][j]) cnt[i]++;
}
cin >> start;
for (int i = 1; i <= n; i++)
{
ans += mp[i][start];
ans %= 20123;
k = start;
mp[i][start] %= cnt[i];
if (!mp[i][start]) mp[i][start] = cnt[i];
if (bol[i][k]) mp[i][start]--;
while (mp[i][start] > 0)
{
k++;
k %= m;
if (bol[i][k]) mp[i][start]--;
}
start = k;
}
cout << ans;
return 0;
}
```