基础数论(数学)30题

什么都不会的蒟蒻开始打基础了\(qwq\)

\((5/30)\)

CF1166E The LCMs Must be Large

考虑集合\(\{a,b,c\}\)

• 对于任意两次限制交集为空，则不可能
  考虑两次限制分别为\(\{a\},\{c\}\)，则\(lcm_a>lcm_{b,c},lcm_a>lcm_{a,c}\)，又\(lcm_{b,c}≥lcm_b,lcm_{a,c}≥lcm_a\)
  则\(lcm_a>lcm_{b,c}≥lcm_b>lcm_{a,c}≥lcm_a\)，显然出现了矛盾

• 对于任意两次限制交集不为空，则可以构造出
  每次限制的集合里的数乘上不相同的质数\(p_i\)，\(\{p_1,p_2,...,p_m\}\)，由于是求\(lcm\)，则每个集合\(lcm\)为\(\prod\limits_{i=1}^m p_i\)，显然补集会小于这个

CF1165D Almost All Divisors

如果有解，排序后首项*末项\(num\)为答案，双指针一直往中间移显然一定乘积都\(num(\)由于\(d_i\)均不同\()\)

还需要特判是否所给的数为\(num\)完整因子，\(num=\prod\limits_{i}p_i^{k_i}\)，则因子数为\(\prod\limits_i k_i+1\)

CF1110C Meaningless Operations

假设\(a\)有\(x\)位，\(b=(2^x-1)\oplus a\)，显然\(b\)一定小于\(a\)，则\(gcd(a\oplus b,a\And b)=gcd(2^x-1,0)=2^x-1\)，显然答案最多有\(x\)位这已经是最优的了

但要求\(b!=0\)，如果\(a=2^x-1\)就不合法了，我们单独考虑

\(gcd((2^x-1)\oplus b,(2^x-1)\And b)=gcd(2^x-1-b,b)=gcd(2^x-1,b)\)，则答案为小于\(2^x-1\)且为最大因子的数

CF1159B Expansion coefficient of the array

\(k≤\frac{min(a_i,a_j)}{|i-j|}\)，把\(a_i\)当作最小值，如果\(a_i>a_j\)，也不会让限制变化

转换为\(k≤\frac{a_i}{|i-j|}\)，为了\(O(1)\)达到限制\(|i-j|=max(i-1,n-i)\)

\(ans=min_{i=1}^n \frac{a_i}{max(i-1,n-i)}\)

CF1158A The Party and Sweets

CF1091D New Year and the Permutation Concatenation

\(next\_permutation\)的求法：

• 找到最长降序后缀，记长度为\(len\)，记该后缀前一个数字为\(x(a_{n-len})\)
  找到后缀中第一个大于\(x\)的数并交换位置
  将后缀\(len\)升序排列

两个相邻的排列\(S,T\)，选\(S\)的后缀\(k\)，\(T\)的前缀\(n-k\)，需要保证\(T\)的后缀\(k\)相似于\(S\)的后缀\(k\)
而确定\(S\)的前缀\(n-k\)里的，则相似的部分是连续的：后缀\(k\)从升序\((\)字典序最小\()\)到降序\((\)字典序最大\()\)的过程

故枚举\(k\)，确定前缀\(n-k\)，再确定后缀\(k\)的排序个数
\(n!+\sum\limits_{i=1}^{n-1}A_n^i\cdot((n-i)!-1)\)

CF1091C New Year and the Sphere Transmission

朴素：枚举\(k\)，\(p\equiv xk(mod~n)\)，\(xk+yn=p\longrightarrow gcd(k,n)|p\)
由于\(p\)是属于\(n\)某因子的，很多\(k\)与\(n\)的\(gcd\)相同，统计一个就好了

• 故\(k\)仅需枚举\(n\)因子即可

假设枚举\(n\)因子\(s\)，\(s|p\)，由于是因子，故走的位置是正好一个环，等差数列即可

• \(\frac{(1+1+n-s)\cdot \frac{n}{s}}{2}\)