Project Euler 446

题目

Retractions B

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\).

\(\displaystyle F(N)=\sum_{n=1}^NR(n^4+4)\).

\(F(1024)=77532377300600\).

Find \(F(10^7)\).

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

解决方案

第445题直接给出了如下关于\(R(n)\)的式子，将\(n\)写成质因数分解的形式\(n=\prod_{i=1}^k p_i^{e_i}\)。那么有：

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

可以发现，通过因式分解，有\(n^4+4=((n+1)^2+1)((n-1)^2+1)\)。

因此，考虑对\(t(x)=x^2+1\)进行分解，那么就有\(n^4+4=t(n-1)\cdot t(n+1)\)。需要注意的是，当\(n\)为偶数时，\(\gcd(t(n-1),t(n+1))=2\)，否则\(\gcd(t(n-1),t(n+1))=1\)。因此考虑\(n^4+4\)的因式分解时，需要单独考虑质因子\(2\)。另一方面，不难证明，\(4\nmid t(n)\)，因此\(n^4+4\)可以是\(4\)的倍数，但必定不能是\(8\)的倍数。

对\(t(n)\)的分解采用第216题的方法：如果\(p\mid t(n)\)，那么\(p\mid t(kp\pm n)\)，其中\(k>0\)。

代码

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

const int N=10000000;
const int M=N+1;
ll mod=1000000007;

ll p[M+4],f[M+4];
int main(){
    for(int i=0;i<=M;i++){
        p[i]=1ll*i*i+1;
        if(i&1) p[i]>>=1;
        f[i]=1;
    }
    for(int i=2;i<=M;i++){
        ll q=p[i];
        if(q>1){
            for(ll j=i;j<=M;j+=q){
                ll m=1;
                for(;p[j]%q==0;p[j]/=q,m*=q);
                f[j]=f[j]*(m+1)%mod;
            }
            //似乎下面这一段不进行筛法也可以，原因尚未知。
            /*for(ll j=q-i;j<=M;j+=q){
                ll m=1;
                for(;p[j]%q==0;p[j]/=q,m*=q);
                f[j]=f[j]*(m+1)%mod;
            }
            */
        }
    }
    ll ans=0;
    for(int n=1;n<=N;n++){
        ll u=1ll*n*n%mod;
        u=(u*u+4)%mod;
        ll v=f[n-1]*f[n+1]%mod;
        // 当n为偶数时，n^4+4是4的倍数，但不是8的倍数。
        if(n%2==0) v=(v*5)%mod;
        ans+=v-u;
    }
    ans=(ans%mod+mod)%mod;
    printf("%lld\n",ans);
}