2020年3月22日小测赛后总结

# 赛后总结 这次比赛我的分数还挺尴尬的……其实主要是时间问题，题目基本来不及实现 ~~话说为什么这次测试的题目背景都这么奇怪~~ ## 第一题：神炎皇 ### 题面 【问题描述】 神炎皇乌利亚很喜欢数对，他想找到神奇的数对。 对于一个整数对(a,b)，若满足a+b<=n且a+b是ab的因子，则成为神奇的数对。请问这样的数对共有多少呢？ 【输入格式】 一行一个整数n。 【输出格式】 一行一个整数表示答案，保证不超过64位整数范围。 【数据范围与约定】 对于20%的数据n<=1000； 对于40%的数据n<=100000； 对于60%的数据n<=10000000； 对于80%的数据n<=1000000000000； 对于100%的数据n<=100000000000000。 ### 思路 首先，看一眼数据范围，放弃模拟 因为 $gcd(a, b)$能同时整除 $a + b$ 与 $ab$ ，设$d = gcd(a, b)$，$a = xd,b = yd$，有 $$x + y | dxy$$ 又因为$gcd(x, y) = 1$ $$x + y | d$$ 设$d = k(x + y)$，因为$a + b \leq n$ $$k(x + y)^2 \leq n$$ $$k \leq \frac{n}{(x + y)^2}$$ 因为$k(x + y)^2 \leq n$ $$(x + y) \leq \sqrt{n}$$ 因此$(x + y)$的范围为$1$~$\sqrt{n}$，$(x, y)$的对数为： $$\sum_{i=1}^{\sqrt{n}} \phi(i)$$ 则$(a, b)$的对数为： $$\sum_{i=1}^{\sqrt{n}} \frac{\phi(i)n}{i^2}$$ ### 评测结果 ~~样例错，原地爆炸~~ ## 第二题：降雷皇 ### 题面 【问题描述】 降雷皇哈蒙很喜欢雷电，他想找到神奇的电光。 哈蒙有n条导线排成一排，每条导线有一个电阻值，神奇的电光只能从一根导线传到电阻比它大的上面，而且必须从左边向右传导，当然导线不必是连续的。 哈蒙想知道电光最多能通过多少条导线，还想知道这样的方案有多少。 【输入格式】 第一行两个整数n和type。type表示数据类型 第二行n个整数表示电阻。 【输出格式】 第一行一个整数表示电光最多能通过多少条导线。 如果type=1则需要输出第二行，表示方案数，对123456789取模。 【数据范围与约定】 对于20%的数据n<=10； 对于40%的数据n<=1000； 对于另外20%的数据type=0； 对于另外20%的数据保证最多能通过不超过100条导线； 对于100%的数据n<=100000,电阻值不超过100000。 ### 思路 最长上升子序列的题 第一问是最长上升子序列模版； ~~第二问卡住了~~ ## 总结 ~~菜是原罪~~