首页 > 其他分享 >UVA10852 的题解

UVA10852 的题解

时间:2024-01-28 10:55:18浏览次数:28  
标签:UVA10852 ch read 题解 leq while

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

相关文章

  • 洛谷题解-P3003 [USACO10DEC] Apple Delivery S (dijkstra)
    题目描述Bessiehastwocrispredapplestodelivertotwoofherfriendsintheherd.Ofcourse,shetravelstheC(1<=C<=200,000)cowpathswhicharearrangedastheusualgraphwhichconnectsP(1<=P<=100,000)pasturesconvenientlynumb......
  • CF765F Souvenirs 题解
    题目链接:CF或者洛谷想了很久,然后想起做过的一道题:秃子酋长,一开始以为差不多,结果写着写着就发现不对劲了。最后写出了个神仙回滚莫队解法,感觉很妙,记录下。进入神仙分析时刻首先,我们来考虑一个事实,加上一个数以后,如果能找到它的前后驱,那么可以立马更新最优解,这个也即是瓶颈点。......
  • ABC338 题解(A-E)
    前言:F,G后续补充。A题意判断一个字符串,是否满足只有第一位为大写字母,其余为小写字母。Sol字面意思模拟即可。Code#include<bits/stdc++.h>#definelllonglong#defineN200005#defineendl"\n"#definefifirst#definesesecondusingnamespacestd;constll......
  • AndroidStudio 编辑xml布局文件卡死问题解决
    之前项目编写的都是正常,升级AndroidStudio后编辑布局文件就卡死,还以为是AndroidStudio文件。其实不然,我给整个项目增加了版权声明。所以全部跟新后,布局文件也增加了版权声明。估计AndroidStudio在解析布局文件时候因为有版权声明的原因导致卡死,所以删除版权声明就可以了。可以......
  • 洛谷题解-P1821 [USACO07FEB] Cow Party S
    https://www.luogu.com.cn/problem/P1821题目描述寒假到了,nnn头牛都要去参加一场在编号为xxx的牛的农场举行的派对,农场之间有mmm条有向路,每条路都有一定的长度。每头牛参加完派对后都必须回家,无论是去参加派对还是回家,每头牛都会选择最短路径,求这nnn头牛的最短路径(一个......
  • 洛谷题解-P1673 [USACO05FEB] Part Acquisition S
    https://www.luogu.com.cn/problem/P1673题目描述奶牛们接到了寻找一种新型挤奶机的任务,为此它们准备依次经过N(1≤N≤5×104)N(1\leN\le5\times10^4)N(1≤N≤5×104)颗行星,在行星上进行交易。为了方便,奶牛们已经给可能出现的K(1≤K≤103)K(1\leK\le10^3)K(1≤K≤103)......
  • CF739A Alyona and mex 题解
    题目传送门前置知识贪心|构造解法从贪心的角度分析,最小的\(\operatorname{mex}\)仅会与长度最小的区间有关;另外为使得\(\operatorname{mex}\)最大,当\(\operatorname{mex}\)等于区间长度的时候即为所求。记\(ans\)表示此时得到的答案。构造序列时,长度最小的区间一定......
  • CF1433E Two Round Dances 题解
    题目传送门前置知识圆排列解法\(\dfrac{Q_{n}^{\frac{n}{2}}Q_{\frac{n}{2}}^{\frac{n}{2}}}{A_{2}^{2}}\)即为所求。同时因为\(n\le20\)和没有模数,所以不需要处理逆元,暴力算即可。代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineu......
  • 洛谷 P1749 [入门赛 #19] 分饼干 II 题解
    题目传送门先给结论:记\(S=1+2+\dots+k\),则当\(N\geS\)时为YES,当\(N<S\)时为NO。严谨一点,证明如下:若能成功分配饼干,记\(k\)名小朋友拿到的饼干数量分别为\(a_1,a_2,\dots,a_k\)。由于饼干数量各不相同且均为整数,不妨设\(a_1<a_2<\dots<a_k\),则\(a_2\gea_1+1,a_3\g......
  • 题解 NOIP2014 提高组-联合权值
    题解NOIP2014提高组-联合权值基本思路:以每个点为中转点,则与之相邻的点组成的点对都可产生联合权值,并且全覆盖。主要总结一下两种求权值和的思路:思路1(容斥):记与\(u\)相邻的点的集合为\(A\),则点\(u\)产生的贡献为\[ans_u=(\sum_{v\inA}w_i)^2-\sum_{v\inA}w_v\times......