奇怪の公式：数论、素数筛、矩阵、欧拉定理
题意简述
给出 f(n,x,y)f(n,x,y)f(n,x,y)、gig_igi 、h(x)h(x)h(x) 的定义，求 h((gcd(gn,gx+y) mod 105)!)h((\gcd{(g_n,g_{x+y})} \bmod 10^5)!)h((gcd(gn ,gx+y )mod105)!) 的值。
公式化简
公式 1
fn,x,y=(∑0≤i,2∣inCni+∑i=0n(∑j=0nyjxn−jCnj)Cni)mod 109+7f_{n,x,y}=(\sum_{0 \le i,2|i}^{n}C_n^i + \sum_{i=0}^{n}(\sum_{j=0}^{n}y^jx^{n-j}C_n^j)C_n^i)\mod 10^9+7 fn,x,y =(0≤i,2∣i∑n Cni +i=0∑n (j=0∑n yjxn−jCnj )Cni )mod109+7
由引理
(x+y)n=∑i=0nyixn−iCni(x+y)^n=\sum_{i=0}^{n}y^ix^{n-i}C_n^i (x+y)n=i=0∑n yixn−iCni
带入 x=1,y=1x=1,y=1x=1,y=1 可得
∑0≤inCni=∑i=0n1i1n−iCni=(1+1)n=2n\sum_{0 \le i}^{n}C_n^i=\sum_{i=0}^{n}1^i1^{n-i}C_n^i=(1+1)^n=2^n 0≤i∑n Cni =i=0∑n 1i1n−iCni =(1+1)n=2n
同理，带入 x=1,y=−1x=1,y=-1x=1,y=−1 可得
(1+(−1))n=∑i=0n(−1)i1n−iCni=0=∑i=0n(−1)iCni=Cn0−Cn1+Cn2−Cn3+⋯+(−1)nCnn→Cn0+Cn2+⋯=Cn1+Cn3+Cn5+⋯→∑0≤i,2∣inCni=∑0≤i,2∣(i+1)nCni→2∑0≤i,2∣inCni=∑0≤inCni=2n→∑0≤i,2∣inCni=2n2=2n−1\begin{aligned} (1+(-1))^n \\ =\sum_{i=0}^{n}(-1)^i1^{n-i}C_n^i=0 \\ =\sum_{i=0}^n(-1)^iC_n^i \\
=C_n^0-C_n^1+C_n^2-C_n^3+\cdots+(-1)^nC_n^n \\ \to C_n^0+C_n^2+\cdots =C_n^1+C_n^3+C_n^5+\cdots \\ \to \sum_{0 \le i,2|i}^{n}C_n^i =\sum_{0 \le i,2|(i+1)}^{n}C_n^i \\ \to 2\sum_{0 \le i,2|i}^{n}C_n^i=\sum_{0 \le i}^{n}C_n^i=2^n \\ \to \sum_{0 \le i,2|i}^{n}C_n^i=\frac{2^n}{2}=2^{n-1}\end{aligned}
(1+(−1))n=i=0∑n (−1)i1n−iCni =0=i=0∑n (−1)iCni =Cn0 −Cn1 +Cn2 −Cn3 +⋯+(−1)nCnn →Cn0 +Cn2 +⋯=Cn1 +Cn3 +Cn5 +⋯→0≤i,2∣i∑n Cni =0≤i,2∣(i+1)∑n Cni →20≤i,2∣i∑n Cni =0≤i∑n Cni =2n→0≤i,2∣i∑n Cni =22n =2n−1
∑j=0nyjxn−jCnj=(x+y)n\sum_{j=0}^{n}y^jx^{n-j}C_n^j=(x+y)^n j=0∑n yjxn−jCnj =(x+y)n
∑i=0n(∑j=0nyjxn−jCnj)Cni=∑i=0n(x+y)nCni=(x+y)n2n\sum_{i=0}^{n}(\sum_{j=0}^{n}y^jx^{n-j}C_n^j)C_n^i=\sum_{i=0}^{n}(x+y)^nC_n^i=(x+y)^n2^n i=0∑n (j=0∑n yjxn−jCnj )Cni =i=0∑n (x+y)nCni =(x+y)n2n
fn,x,y=(∑0≤i,2∣inCni+∑i=0n(∑j=0nyjxn−jCnj)Cni)mod 109+7=(2n−1+2n(x+y)n)mod 109+7\begin{aligned} f_{n,x,y}=(\sum_{0 \le i,2|i}^{n}C_n^i + \sum_{i=0}^{n}(\sum_{j=0}^{n}y^jx^{n-j}C_n^j)C_n^i)\mod 10^9+7 \\=(2^{n-1}+2^n(x+y)^n) \mod 10^9+7 \end{aligned} fn,x,y =(0≤i,2∣i∑n Cni +i=0∑n (j=0∑n yjxn−jCnj
)Cni )mod109+7=(2n−1+2n(x+y)n)mod109+7
可用快速幂解决。
公式 2
gi={[i=1](i≤1)(fx,n,x+ygi−1+fy,x+y,ngi−2)mod 109+7(i>1)g_i = \begin{cases} [i = 1] & (i \leq 1) \\ (f_{x,n,x+y}g_{i - 1} + f_{y,x+y,n}g_{i - 2}) \mod 10^9+7& (i \gt 1) \end{cases} gi ={[i=1](fx,n,x+y gi−1 +fy,x+y,n gi−2 )mod109+7 (i≤1)(i>1)
定义p=fx,n,x+y,q=fy,x+y,np=f_{x,n,x+y},q=f_{y,x+y,n}p=fx,n,x+y ,q=fy,x+y,n
即：
gi={[i=1](i≤1)(pgi−1+qgi−2)mod 109+7(i>1)g_i = \begin{cases} [i = 1] & (i \leq 1) \\ (pg_{i - 1} + qg_{i - 2}) \mod 10^9+7& (i \gt 1) \end{cases} gi ={[i=1](pgi−1 +qgi−2 )mod109+7 (i≤1)(i>1)
容易发现这是斐波那契数列，其初始矩阵为：
[p1q0]\begin{bmatrix}p & 1 \\ q & 0\end{bmatrix} [pq 10 ]
可用矩阵快速幂解决。
公式 3
h(x)=∑d=1,x∣dxp∑1≤i∞i×(1−p)i−1(0<p<1)h(x)=\sum_{d=1,x|d}^{x}p\sum_{1 \le i}^{\infty}i \times (1-p)^{i-1}(0 < p <1) h(x)=d=1,x∣d∑x p1≤i∑∞ i×(1−p)i−1(0<p<1)
p∑1≤i∞i×p(1−p)i−1(0<p<1)=p×p∑1≤i∞i×(1−p)i−1\begin{aligned} p\sum_{1 \le i}^{\infty}i \times p(1-p)^{i-1}(0 < p <1) = p \times p\sum_{1 \le i}^{\infty}i \times (1-p)^{i-1} \end{aligned} p1≤i∑∞ i×p(1−p)i−1(0<p<1)=p×p1≤i∑∞ i×(1−p)i−1
定义
k=p∑1≤i∞i×(1−p)i−1=(1−p)0+2(1−p)1+⋅⋅⋅k−(1−p)k=1+2(1−p)+⋅⋅⋅−(1−p)−2(1−p)2−⋅⋅⋅=1+(1−p)+(1−p)2+⋅⋅⋅=∑0≤i∞(1−p)i=1⋅(1−(1−p)n)1−(1−p)(n→∞)=1−(1−p)np(n→∞)\begin{aligned} k=p\sum_{1 \le i}^{\infty}i \times (1-p)^{i-1}=(1-p)^0+2(1-p)^1+\cdot\cdot\cdot \\
k-(1-p)k=1+2(1-p)+\cdot\cdot\cdot-(1-p)-2(1-p)^2-\cdot\cdot\cdot \\ =1+(1-p)+(1-p)^2+\cdot\cdot\cdot \\ =\sum_{0 \le i}^{\infty}(1-p)^i \\ =\frac{1 \cdot(1-(1-p)^n)}{1-(1-p)}(n \to \infty) \\ = \frac{1-(1-p)^n}{p}(n \to \infty) \end{aligned} k=p1≤i∑∞
i×(1−p)i−1=(1−p)0+2(1−p)1+⋅⋅⋅k−(1−p)k=1+2(1−p)+⋅⋅⋅−(1−p)−2(1−p)2−⋅⋅⋅=1+(1−p)+(1−p)2+⋅⋅⋅=0≤i∑∞ (1−p)i=1−(1−p)1⋅(1−(1−p)n) (n→∞)=p1−(1−p)n (n→∞)
因为：
0<p<1→0<(1−p)<10<p<1 \to 0<(1-p)<1 0<p<1→0<(1−p)<1
所以：
(1−p)n(n→∞)=an(0<a<1)(n→∞)→0(1-p)^n(n \to \infty)=a^n(0<a<1)(n \to \infty) \to 0 (1−p)n(n→∞)=an(0<a<1)(n→∞)→0
k−(1−p)k=k−(k−pk)=k−k+pk=pk=∑0≤i∞(1−p)i=1p→k=1p2k-(1-p)k=k-(k-pk)=k-k+pk=pk=\sum_{0 \le i}^{\infty}(1-p)^i = \frac{1}{p} \to k=\frac{1}{p^2} k−(1−p)k=k−(k−pk)=k−k+pk=pk=0≤i∑∞ (1−p)i=p1 →k=p21
即：
p∑1≤i∞i×p(1−p)i−1(0<p<1)=p×k=p×1p2=1pp\sum_{1 \le i}^{\infty}i \times p(1-p)^{i-1}(0 < p <1) = p \times k =p \times \frac{1}{p^2}=\frac{1}{p} p1≤i∑∞ i×p(1−p)i−1(0<p<1)=p×k=p×p21 =p1
p×p∑1≤i∞i×(1−p)i−1=p×1p=1p \times p\sum_{1 \le i}^{\infty}i \times (1-p)^{i-1} =p \times \frac{1}{p}=1 p×p1≤i∑∞ i×(1−p)i−1=p×p1 =1
h(x)=∑d=1,x∣dxp∑1≤i∞i×(1−p)i−1(0<p<1)=∑d=1,x∣dxk2(k=1)=τ(x)h(x)=\sum_{d=1,x|d}^{x}p\sum_{1 \le i}^{\infty}i \times (1-p)^{i-1}(0 < p <1)=\sum_{d=1,x|d}^{x}k^2(k=1)=\tau{(x)} h(x)=d=1,x∣d∑x p1≤i∑∞ i×(1−p)i−1(0<p<1)=d=1,x∣d∑x k2(k=1)=τ(x)
由引理
τ(x)=∏p≤x(∑k=1∞(⌊xpk⌋)+1)(p∈Prime)\tau{(x)}=\prod_{p \le x} (\sum_{k=1}^{\infty}\left(\lfloor\dfrac{x}{p^k}\rfloor\right)+1)(p \in \text{Prime}) τ(x)=p≤x∏ (k=1∑∞ (⌊pkx ⌋)+1)(p∈Prime)
可得
h(x!)=∏p≤x!(∑k=1∞(⌊x!pk⌋)+1)(p∈Prime)h(x!)=\prod_{p \le x!} (\sum_{k=1}^{\infty}\left(\lfloor\dfrac{x!}{p^k}\rfloor\right)+1)(p \in \text{Prime}) h(x!)=p≤x!∏ (k=1∑∞ (⌊pkx! ⌋)+1)(p∈Prime)
计算结果
gcd(gn,gx+y)\gcd{(g_n,g_{x+y})} gcd(gn ,gx+y )
由引理得：
gcd(gn,gx+y)=ggcd(n,x+y)\gcd{(g_n,g_{x+y})}=g_{\gcd{(n,x+y)}} gcd(gn ,gx+y )=ggcd(n,x+y)
易得：
h((gcd(gn,gx+y)mod 105)!)→h(x!)(x=gcd(gn,gx+y)mod 105)h((\gcd{(g_n,g_{x+y})} \mod 10^5)!) \to h(x!)(x=\gcd{(g_n,g_{x+y})} \mod 10^5) h((gcd(gn ,gx+y )mod105)!)→h(x!)(x=gcd(gn ,gx+y )mod105)
xxx 可 O(log2(max(n,x+y)))O(log _2{(\max{(n,x+y)})})O(log2 (max(n,x+y))) 得出，h(x!)h(x!)h(x!) 可用素数筛 O(x)(x<105)O(x)(x < 10^5)O(x)(x<105)解决
正解
时间复杂度：O(Mod)O(Mod)O(Mod)，其中 Mod≤105Mod\le10^5Mod≤105
预计得分：200pts200pts200pts
