这是一些CF上的simple??的数论题。QAQ
第一波-2017.8.23
CF222C 给出两个集合,第一个集合数的乘积是分子,第二个集合的数的乘积是分母,要求够造一个同样大小的集合,但是得到的分数是化简过的。$1≤n,m≤10^5,ai,bi<=10^7$
质因数分解,构造。考虑首先筛出$10^7$内的所有素数,然后对所有数质因数分解。最后暴力消除即可。为了保证一定能存在答案,只需要在原来数的基础上消除即可。
CF446C 给定$n$个元素的数组$a[]$。操作$1, l, r$。要求对于$l<=i<=r$,$a[i] += f[i-l+1]$。询问$2,l,r$。返回$\sum_{i=l}^{r} a[i]$,对$10^9+9$取模。其中$f[i]$为斐波那契数列,$f[1]=1,f[2]=1$。$n,m<=300000$
斐波那契数列,线段树维护等比数列。本题似乎无从下手,因为每一个数增加的值不同。事实上,我们可以利用斐波那契数列的的通项公式(可以用母函数证明,是线性常系数其次递推关系,可窝不会)。
$$\large fib(i) = \frac {1} {\sqrt{5}} \left( \left(\frac {1+\sqrt{5}} {2}\right)^n + \left( \frac {1-\sqrt{5}} {2} \right)^n \right)$$
令$\large q1= \frac {1+\sqrt{5}} {2}, q2 = \frac {1-\sqrt{5}} {2}$,于是我们只需要维护两个等比数列即可,由于公比是$q1,q2$不变,所以直接利用等比数列求和即可,用线段树维护区间和。注意,本题需要得到$q1,q2$在模意义下的值,只需要暴力算出$\sqrt5$即可。
顺便提一下,我们需要利用等比数列求和公式$\large \frac {q^n-1} {q-1}$ ,但是本题中$q1,q2$满足$q^2-q-1=0$,就是说$rev(q-1)=q$,原来的公式就变为了$q^{n+1}-q$,足以见得斐波那契数列的神奇。
CF711E,2A。给定$n,k$,已知一年有$2^n$天,选取$k$个人,两个人的生日是在同一天的的概率。要求答案写成最简分数。$n,k<=10^{18}$
欧拉定理降幂,组合相关。首先需要特判一个情况,就是$k>2^n$概率就是$1$。从反面情况入手,总共生日的方案数为$A=2^{nk}$,所有人的生日互不相同的情况为$B=A_{2^n}^{k}$。答案即为$\large \frac {A-B} A$ 。注意到,$A$的质因数仅有$2$,所以我们需要知道$B$中质因数$2$的个数即可。考虑其展开式,
$$\large B = A_{2^n}^k = 2^n \times (2^n-1) \times (2^n-2) \times … \times (2^n-k+1)$$
首先,$2^n$中有$n$个,然后若存在$2^n-a2^b(b<n)$,那么显然这一项含有$b$个质因数$2$,所以我们只要统计$(k-1)!$的质因数$2$的个数即可。
但是$A=2^{nk}$,指数过大,应该如何处理。考虑降幂大法,欧拉定理:
$$\large a^{\varphi(m)}\equiv a^{0} \pmod m$$
所以指数对$\varphi(m)$取模即可。
CF121C,1A。对于一个数,如果它仅包含$4$或$7$,则称之为幸运数。求$[1,n]$的第$K$个置换,有多少幸运数位于的位置也是幸运数。$n,k<=10^9$
观察,求第$K$排列。注意到$k$很小,当$n>=14$时,最前面的$n-13$位是不发生改变的。而且$10^9$内的幸运数只有$1023$个,所以,对于前面的数字,我们暴力计算,后面的,暴力求出第$K$排列即可。
CF772C,1A。给定$m$和$n$个整数$ai(0<=ai<=m-1)$,请您构造一个最长的序列,满足对于所有前缀积对$m$取模,它们互不相同,且不等于任意一个$ai$。$n,m<=200,000$
GCD,DAG最长路。考虑最后一个数与$m$的$\gcd\ t$,可以注意到,这个数通过乘与$m$互质的数,可以得到任意一个与$m$的$\gcd$为$t$。同样我们也可以乘上一个与$m$不互质的数,得到与$m$的$\gcd$为$kt$的数。DP得到最长路后,dfs输出答案即可。
考虑证明这一点。其中$kax \equiv bcx \pmod m$,$x$是原来最后一个数与$m$的$gcd$(所以$a$与$m$互质),$cx$是新的$gcd$,由乘上一个$k$得到。然后$ka \equiv bc \pmod {\frac m x}$ ,因为$a$与$m$互质,所以一定存在$k$。
CF396B,1A。定义函数$v(n)$为不大于$n$的最大素数。定义函数$u(n)$为大于$n$的最小素数。求$\large \sum \frac 1 {v(i) \times u(i)}(2<=i<=n)$。$T<=500,n<=1e9$
裂项,素数判断。思路很巧妙,考虑到,
$$ (u(n)-v(n)) \times \frac 1 {v(n) \times u(n)} = \frac 1 {v(n)} - \frac 1{u(n)}$$
所以我们就可以裂项相消了,于是,
$Ans = 1/2 -1/3 + 1/3 - 1/5 + …….. -1/v + \frac 1 {v\times u\times (n-v+1)}$
消掉,约分即可。
CF283D。对于$(x,y)$,如果满足$x$可以表示为连续$y$个整数之和,则它是酷的。如果$(a1,a2),(a2,a3),..,(an-1,an)$都是酷的。那么整个序列就是酷的。给定长度为$n$的序列,求最少改变几个数字,使得整个序列是酷的。$n<=5000$
数论,动态规划。首先考虑$(x,y)$符合要求的条件,根据等差数列求和公式,可以知道:当$y$为奇数时,只要$x$是$y$的倍数;当$y$为偶数时,只要$2x$是$y$的奇数倍即可。观察第二个条件,也就是说$x$质因数$2$的个数比$y$质因数$2$的个数少$1$,对于其它部分$x’$是$y’$的倍数。受此启发考虑令$a[i]=2^{x[i]}\times y[i]$,以方便状态的转移。
定义$f[i]$表示$i$是不变的,以$i$结尾的序列,需要满足条件,可以不改变的最长子序列。于是对于一个状态$i$我们寻找$j$同样是不改变的。
- 如果$a[i]$是奇数($x[i]=0$),且$y[j] \bmod y[i] = 0$ ,则$f[i]$可以由$f[j]$转移过来
- 如果$x[i]!=0$,条件就比较复杂。首先$y[j] \bmod y[i] = 0$是一个必要条件,接下来考虑$x[i]$与$x[j]$
- 考虑$x[i]$向前移动,如果向前移动一位,则$x$必定会减一,于是会出现两种情形。-
- 一是$x$还没有到$j$已经变为了$0$(也就是$x[i]<i-j$),变为了奇数,一定能够在最后一次变为$x[i]$。
- 二是$x$到$j$时仍然不是$0$,这就要求$x=x[j]$,也就是说$x[i]-x[j]=i-j$。
至此,问题得到完整的解决。注意一点,我们可以在序列的最后增加一个数$1$使得之前所有状态的答案会聚到这一状态。