数字类题目

重要观察

$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互质，所以可以简单完成。

希望我们计算一个区间的乘积，判断是否可能达到给定的输出。
数据规模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=（总提交次数-过题数量）/总提交次数

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

GCD二级结论

$lcm(a,b)*gcd(a,b)=ab$

$gcd(a,b) = gcd(a,|b-a|)$

$gcd(a,b,c)=1等价于存在ax+by+cz =1$

$gcd(a,b) = g * gcd(a >> k,b >> k)\,(g = 2 ^ k)$

$gcd(a^{n-1},a^{m-1})=a^{gcd(n,m)-1}$

$gcd(f_n,f_m)=f_{gcd(n,m)}$

斐波那契数列

那么接下来我们计算阶乘和逆元就能解答了（
（怎么这么麻烦，没招了）