奇怪の公式：数论、素数筛、矩阵、欧拉定理

题意简述

给出 $f(n,x,y)$、$g_i$、$h(x)$ 的定义，求 $h((\gcd{(g_n,g_{x+y})} \bmod 10^5)!)$ 的值。

公式化简

公式 1

$$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$$

由引理

$$(x+y)^n=\sum_{i=0}^{n}y^ix^{n-i}C_n^i$$

带入 $x=1,y=1$ 可得

$$\sum_{0 \le i}^{n}C_n^i=\sum_{i=0}^{n}1^i1^{n-i}C_n^i=(1+1)^n=2^n$$

同理，带入 $x=1,y=-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}$$

$$\sum_{j=0}^{n}y^jx^{n-j}C_n^j=(x+y)^n$$

$$\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$$

$$\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}$$

可用快速幂解决。

long long pw(long long a,long long b,long long mod) {
    long long ans=1;
    a%=mod;
    while (b){
        if (b&1){
        	ans=ans*a%mod;
		}
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
long long f(long long n, long long x, long long y){
    return ((pw(x+y,n,MOD)*pw(2,n,MOD))%MOD+pw(2,n-1,MOD))%MOD;
}

公式 2

$$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}$$

定义$p=f_{x,n,x+y},q=f_{y,x+y,n}$
即：

$$g_i = \begin{cases} [i = 1] & (i \leq 1) \\ (pg_{i - 1} + qg_{i - 2}) \mod 10^9+7& (i \gt 1) \end{cases}$$

容易发现这是斐波那契数列，其初始矩阵为：

$$\begin{bmatrix}p & 1 \\ q & 0\end{bmatrix}$$

可用矩阵快速幂解决。

struct Mat{
    long long mat[2][2];
    Mat(){
        mat[0][0]=mat[1][1]=1;
        mat[0][1]=mat[1][0]=0;
    }
    Mat operator*(const Mat& ot) const{
        Mat res;
        res.mat[0][0]=(mat[0][0]*ot.mat[0][0]+mat[0][1]*ot.mat[1][0])%MOD;
        res.mat[0][1]=(mat[0][0]*ot.mat[0][1]+mat[0][1]*ot.mat[1][1])%MOD;
        res.mat[1][0]=(mat[1][0]*ot.mat[0][0]+mat[1][1]*ot.mat[1][0])%MOD;
        res.mat[1][1]=(mat[1][0]*ot.mat[0][1]+mat[1][1]*ot.mat[1][1])%MOD;
        return res;
    }
};
Mat mat_pw(Mat a,long long b){
    Mat res;
    while (b) {
        if (b&1){
        	res=res*a;
		}
        a=a*a;
        b>>=1;
    }
    return res;
}
long long fib(long long n){
    if (n==0){
    	return 0;
	}
    Mat base;
    base.mat[0][0]=f(x,n,x+y);
    base.mat[0][1]=f(y,x+y,n);
    base.mat[1][0]=1;
    base.mat[1][1]=0;
    Mat res=mat_pw(base,n-1);
    return res.mat[0][0];
}

公式 3

$$h(x)=\sum_{d=1,x|d}^{x}p\sum_{1 \le i}^{\infty}i \times (1-p)^{i-1}(0 < p <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}$$

定义

$$\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}$$

因为：

$$0<p<1 \to 0<(1-p)<1$$

所以：

$$(1-p)^n(n \to \infty)=a^n(0<a<1)(n \to \infty) \to 0$$

$$k-(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}$$

即：

$$p\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}$$

$$p \times p\sum_{1 \le i}^{\infty}i \times (1-p)^{i-1} =p \times \frac{1}{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)=\sum_{d=1,x|d}^{x}k^2(k=1)=\tau{(x)}$$

由引理

$$\tau{(x)}=\prod_{p \le x} (\sum_{k=1}^{\infty}\left(\lfloor\dfrac{x}{p^k}\rfloor\right)+1)(p \in \text{Prime})$$

可得

$$h(x!)=\prod_{p \le x!} (\sum_{k=1}^{\infty}\left(\lfloor\dfrac{x!}{p^k}\rfloor\right)+1)(p \in \text{Prime})$$

long long g(long long i,long long x,long long y) {
    if (i<=1){
        long long fi=f(i,x,y);
        long long fx=f(x,i,y-1);
        long long pff=pw(fi,fx,MOD);
        return pff;
    }
    return fib(i);
}

计算结果

$$\gcd{(g_n,g_{x+y})}$$

由引理得：

$$\gcd{(g_n,g_{x+y})}=g_{\gcd{(n,x+y)}}$$

易得：

$$h((\gcd{(g_n,g_{x+y})} \mod 10^5)!) \to h(x!)(x=\gcd{(g_n,g_{x+y})} \mod 10^5)$$

$x$ 可 $O(log _2{(\max{(n,x+y)})})$ 得出，$h(x!)$ 可用素数筛 $O(x)(x < 10^5)$解决

vector<int> p;
bool vis[1000010];
void init(){
    memset(vis,1,sizeof vis);
    vis[0]=vis[1]=0;
    for (int i=2;i<1000010;i++) {
        if (vis[i]){
            p.push_back(i);
            for (int j=2*i;j<1000010;j+=i) {
                vis[j]=0;
            }
        }
    }
}

正解

#include <bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
long long n,x,y;
long long pw(long long a,long long b,long long mod) {
    long long ans=1;
    a%=mod;
    while (b){
        if (b&1){
        	ans=ans*a%mod;
		}
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
long long f(long long n, long long x, long long y){
    return ((pw(x+y,n,MOD)*pw(2,n,MOD))%MOD+pw(2,n-1,MOD))%MOD;
}
struct Mat{
    long long mat[2][2];
    Mat(){
        mat[0][0]=mat[1][1]=1;
        mat[0][1]=mat[1][0]=0;
    }
    Mat operator*(const Mat& ot) const{
        Mat res;
        res.mat[0][0]=(mat[0][0]*ot.mat[0][0]+mat[0][1]*ot.mat[1][0])%MOD;
        res.mat[0][1]=(mat[0][0]*ot.mat[0][1]+mat[0][1]*ot.mat[1][1])%MOD;
        res.mat[1][0]=(mat[1][0]*ot.mat[0][0]+mat[1][1]*ot.mat[1][0])%MOD;
        res.mat[1][1]=(mat[1][0]*ot.mat[0][1]+mat[1][1]*ot.mat[1][1])%MOD;
        return res;
    }
};
Mat mat_pw(Mat a,long long b){
    Mat res;
    while (b) {
        if (b&1){
        	res=res*a;
		}
        a=a*a;
        b>>=1;
    }
    return res;
}
long long fib(long long n){
    if (n==0){
    	return 0;
	}
    Mat base;
    base.mat[0][0]=f(x,n,x+y);
    base.mat[0][1]=f(y,x+y,n);
    base.mat[1][0]=1;
    base.mat[1][1]=0;
    Mat res=mat_pw(base,n-1);
    return res.mat[0][0];
}
long long g(long long i,long long x,long long y) {
    if (i<=1){
        long long fi=f(i,x,y);
        long long fx=f(x,i,y-1);
        long long pff=pw(fi,fx,MOD);
        return pff;
    }
    return fib(i);
}
vector<int> p;
bool vis[1000010];
void init(){
    memset(vis,1,sizeof vis);
    vis[0]=vis[1]=0;
    for (int i=2;i<1000010;i++) {
        if (vis[i]){
            p.push_back(i);
            for (int j=2*i;j<1000010;j+=i) {
                vis[j]=0;
            }
        }
    }
}
long long cd(long long x){
    long long ans=1;
    for (int ps:p){
        long long et=0;
        long long pr=ps;
        while (pr<=x){
            et+=x/pr;
            if (pr>x/ps){
				break;
			}
            pr*=ps;
        }
        ans=(ans*(et+1))%MOD;
    }
    return ans;
}
int main() {
    init();
    cin>>n>>x>>y;
    long long gnxy=__gcd(n,x+y);
    long long gg=g(gnxy,x,y);
    long long gm=gg%(100000);
    long long phi=cd(gm);
    cout<<phi<<endl;
    return 0;
}

时间复杂度：$O(Mod)$，其中 $Mod\le10^5$
预计得分：$200pts$