Project Euler 445

题目

Retractions A

For every integer \(n>1\), the family of functions \(f_{n,a,b}\) is defined by

$f_{n,a,b}(x)a x + b n,,, $ for \(a,b,x\) integer and \(0< a <n, 0 \le b < n,0 \le x < n\).

We will call \(f_{n,a,b}\) a retraction if \(\,\,\, f_{n,a,b}(f_{n,a,b}(x)) \equiv f_{n,a,b}(x) \mod n \,\,\,\) for every \(0 \le x < n\).

Let \(R(n)\) be the number of retractions for \(n\).

You are given that

\(\displaystyle \sum_{k=1}^{99\,999} R\left(\binom {100\,000} k\right) \equiv 628701600 \mod 1\,000\,000\,007\).

Find \(\displaystyle \sum_{k=1}^{9\,999\,999} R\left(\binom {10\,000\,000} k\right)\).

Give your answer modulo \(1\,000\,000\,007\).

解决方案

令\(N=10^7\)。

如题，\(f_{n,a,b}(f_{n,a,b}(x)) \equiv f_{n,a,b}(x) \pmod n\)将意味着：

\(a(ax+b)+b\equiv ax+b \pmod n\)

整理后，得到\(a(a-1)x+ab\equiv0\pmod n\)。

不失一般性，令\(x=0\)，那么就能够得到\(ab\equiv 0 \pmod n\)。

再令\(x=1\)，那么就得到\(a(a-1)+ab\equiv 0\pmod n\)，去除\(ab\)后，也就得到\(a(a-1)\equiv 0\pmod n\)。

将\(n\)写成质因数分解的形式：\(n=\prod_{i=1}^k p_i^{e_i}\)，那么对于任意\(i\in[1,k]\)，都有\(a(a-1)\equiv 0\pmod{p_i^{e_i}},ab\equiv 0\pmod{p_i^{e_i}}\)。因此，我们从中国剩余定理的角度考虑\(R(n)\)的值。

可以发现，\(\gcd(a,a-1)=1\)，因此对于\(a\in[0,p_i^{e_i})\)，要令\(a(a-1)\equiv 0\pmod{p_i^{e_i}}\)，无外乎有以下两种情况：

1. 当\(a\equiv 0\pmod{p_i^{e_i}}\)时，那么可以发现对于任意\(b\in[0,p_i^{e_i})\)，\(ab\equiv 0\pmod{p_i^{e_i}}\)都能满足。此时\(b\)值有\(p_i^{e_i}\)种取法。

2. 当\(a\equiv 1\pmod{p_i^{e_i}}\)时，那么要令\(ab\equiv0\pmod{p_i^{e_i}}\)，只能取\(b=0\)。此时\(b\)仅有一种取法。

综上所述，对于一个\(n\)，最终满足题目条件的不同的\((a,b)\)对数\(R(n)\)为

\[R(n)=\prod_{i=1}^k(p_i^{e_i}+1)-n\]

这里减去\(n\)，是为了减去\(a=0\)时的情况（题目明确\(a>0\)），因为按照中国剩余定理，最终组合产生的结果会等于\(0\)。

因此，题目就变成了维护\(\prod_{i=1}^k(p_i^{e_i}+1)\)的值。

由于本题使用的\(n\)是组合数，通过递推公式\(\dbinom{n}{k}=\dfrac{n-k+1}{k}\cdot\dbinom{n}{k-1}\)，对\(n-k+1\)和\(k\)进行分解并维护即可。

使用组合数的性质\(\dbinom{n}{k}=\dbinom{n}{n-k}\)可以减少一半的计算开销。

对于\(R(n)\)项中的后面那个\(n\)，使用组合数公式优化计算：

\[\sum_{i=0}^n\dbinom{n}{i}=2^n\]

代码

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=10000000;
ll mod=1000000007;

int v[N+4];
int pr[N/5+1000],m=0;
void init(){
    for(int i=2;i<=N;i++){
        if(v[i]==0){
            v[i]=i; pr[++m]=i;
        }
        for(int j=1;j<=m;j++){
            if(pr[j]>v[i]||pr[j]>N/i) break;
            v[i*pr[j]]=pr[j];
        }
    }
}
int p[14],e[14],o=0;
void fact(int n){
    o=0;
    for(;n!=1;){
        p[++o]=v[n];e[o]=0;
        for(;n%p[o]==0;n/=p[o],++e[o]);
    }
}
ll qpow(ll n,ll m){
    ll a=1;
    for(;m;m>>=1){
        if(m&1) a=a*n%mod;
        n=n*n%mod;
    }
    return a;
}
int f[N+4];
int main(){
    init();
    ll ans=0,val=1;
    for(int k=1;k<=N/2;k++){
        fact(N-k+1);
        for(int i=1;i<=o;i++){
            if(f[p[i]]>0) val=val*qpow(qpow(p[i],f[p[i]])+1,mod-2)%mod;
            f[p[i]]+=e[i];
            val=val*(qpow(p[i],f[p[i]])+1)%mod;
        }
        fact(k);
        for(int i=1;i<=o;i++){
            val=val*qpow(qpow(p[i],f[p[i]])+1,mod-2)%mod;
            f[p[i]]-=e[i];
            if(f[p[i]]>0) val=val*(qpow(p[i],f[p[i]])+1)%mod;
        }
        ans=(ans+val*2)%mod;
    }
    if(N%2==0) ans=(ans-val+mod)%mod;
    ans=(ans-qpow(2,N)+2+mod)%mod;
    printf("%lld\n",ans);
}