UVA10852 的题解
题目大意
给定自然数 \(n(100\leq n \leq 10000)\),寻找质数 \(x\le n\),使得 \(p\times x\leq n<(p+1)\times x\) 且 \(n-p\times x\) 最大。
思路
不难发现,\(p\) 其实就是 $\left \lfloor \frac{n}{x} \right \rfloor $,所以,我们只要找到对应的 \(x\),\(p\) 的只就确定了。
那么如何求 \(x\) 的值呢?我们可以考虑枚举。
由于数据范围不大,\(O(n^2)\) 的时间复杂度可以通过此题,所以我们可以先预处理出 \(10000\) 以内的每一个质数,然后再预处理出对于每一个 \(n\) 的 \(x\),查询时只需要输出就可以了。
Code
#include <bits/stdc++.h>
#define fre(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
using namespace std;
typedef long long ll;
const int N = 1e4;
const int INF = 0x3f3f3f3f;
template<class _Tp>
void read(_Tp &s)
{
s = 0;
char ch = getchar(), last = ' ';
while (ch < '0' || ch > '9')
last = ch, ch = getchar();
while (ch >= '0' && ch <= '9')
s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
if (last == '-')
s = -s;
}
bool check_prime(int t)
{
int s = sqrt(t);
for (int i = 2; i <= s; i++)
if (t % i == 0)
return 0;
return 1;
}
int T;
int n;
int pri[N + 5], tot;
int x[N + 5];
int main()
{
for (int i = 2; i <= N; i++)
if (check_prime(i))
pri[++tot] = i;
for (int i = 1; i <= N; i++)
{
x[i] = 1;
for (int j = 1; j <= tot && pri[j] < i; j++)
if (i - (i / pri[j]) * pri[j] > i - (i / x[i]) * x[i])
x[i] = pri[j];
}
read(T);
while (T--)
{
read(n);
printf("%d\n", x[n]);
}
return 0;
}
标签:UVA10852,ch,read,题解,leq,while
From: https://www.cnblogs.com/mgcjade/p/17992559