数字类题目

  • 定义：通常有乘除法，或者时分解质因数之类的

重要观察

$2^{30} >= 10^9$所以一般不需要几个数就能乘到上界，除法的话同理，分解质因数实际上也算乘法。
因此这类题目往往可以比较暴力的解决。因为只要枚举这几个位置即可。

重要例题：

1.题目传送门Strange Machine

  • 重要观察：$log_2(10^9)=30$,所以除去全是1的情况，每次除2最多30次循环就结束了，因此可以暴力解决。除了有1的情况，因为n最大为20，所以最多$20*30$每个数据。

2.题目传送门Even Modulo Pair

  • 重要观察，要塞大量数据来导致超时的话是不可能的，因为在30个数内必然能找到。
    理由：首先如果只有偶数，那么一定有解。（因为严格递增）
    当只有奇数时：
    因为当$y<2x$时，必然有$y \mod x \ = \ y-x \ = \text{偶数}$,因此要构造较大的数据的话，只能让$y \geq x 2$
    要让$y \mod x \ != \text{偶数}$，那么最小只能构造$y=x*2$那么和上一题就一样了。

3.题目传送门Add 0 or K

  • 题目理解，首先要求吧原数组每个元素加上K的若干倍，构成含有相同因子的数组。
  • 重要观察：加完以后，因为含有相同的因子，所以考虑把每个加完以后的数字拆分，得到一串质数，而前29个质数的乘积已经大于$10^9$了，所以直接可以算出最终的共同因子。
    接下来对最后结果化简$a_i+c_ik \equiv 0 (mod\ g)$,所以$c_i=(-a_i)inv_k$
    而k存在$mod \ g$下有逆元，需要g和k互质，所以可以简单完成。

4.题目传送门C-区间乘_2025年广东工业大学新生赛（同步赛）

  • 希望我们计算一个区间的乘积，判断是否可能达到给定的输出。
  • 数据规模n和查询规模q都是$2*10^5$所以不能直接查询。
  • 重要观察：如果把1去掉算法就能变简单，而如果不是全为1的话，查询数据$x \leq 10^9$，所以当不是1的时候，只要30个2就能超过数据范围了，每个位置计算一下，可以直接提取计算可能出现的数字，故最多$30210^5$次计算，查询$q\log_2(x)$次就行了
    所以最终时间复杂度是$O(Tcountq\log_2(q))$
    dirt=（总提交次数-过题数量）/总提交次数

然后注意，只有质因数时可以用，其他的如因子就不行
出现奇偶判断的也不要用这个方法，用奇偶性分析特判