题目

题目大意

\(A\)、\(B\)两人赛马, 最终名次有\(3\)种可能: 并列第一; \(A\)第一\(B\)第二; \(B\)第一\(A\)第二。输入\(n\)(\(1 ≤ n ≤1000\)), 求\(n\)人赛马时最终名次的可能性的个数除以\(10056\)的余数。

阅读全文 »

题目

题目大意

输入一个\(n\)(\(n ≤ 100000\))个元素的正整数序列\(a_1, a_2, \cdots , a_n\)(\(1 ≤ a_i ≤ 10^{12}\)), 求一个连续子序列, 使得该序列中所有元素的最大公约数与序列长度的乘积最大。例如, \(5\)个元素的序列\(30, 60, 20, 20, 20\)的最优解为\(\{60, 20, 20, 20\}\), 乘积为\(4(60, (20, (20, (20, 20)))) = 80\)。

阅读全文 »

UVa 1393 Highways (动态规划)

发表于 2018-09-29 更新于 2024-08-22 分类于 OI

题目

题目大意

有一个\(n\)行\(m\)列(\(1 ≤ n, m ≤ 300\))的点阵, 问: 一共有多少条非水平非竖直的直线至少穿过其中两个点? 例如, \(n = 2\), \(m = 4\)时答案为\(12\), \(n = m = 3\)时答案为\(14\)。

阅读全文 »

UVa 10214 Trees in a Wood. (欧拉函数)

发表于 2018-09-29 更新于 2024-08-22 分类于 OI

题目

题目大意

在满足\(|x| ≤ a\), \(|y| ≤ b\)(\(a ≤ 2000\), \(b ≤ 2000000\))的网格中, 处了原点之外的整点(即\(x\), \(y\)坐标均为整数的点)各种着一棵树。数的半径可以忽略不计, 但是可以相互遮挡。求从原点能看当多少棵树。设这个值为\(K\), 要求输出\(\frac{K}{N}\), 其中\(N\)为网格中树的总数。

阅读全文 »

UVa 11440 Help Tomisu (欧拉函数)

发表于 2018-09-29 更新于 2024-08-22 分类于 OI

题目

题目大意

给定正整数\(N\)和\(M\), 统计\(2\)和\(N!\)之间有多少个整数\(x\)满足: \(x\)的所有素因子都大于\(M\)(\(2 ≤ N ≤ 10^7\), \(1 ≤ M ≤ N\), \(N - M ≤ 10^5\))。输出答案除以\(100000007\)的余数。例如, \(N = 100\), \(M = 10\)时的答案为\(43274465\)。