小x的奇遇-adventure

小x的奇遇-adventure

题意：

给定函数f(n),g(n),求$G_k(n)$
$$f(n)=\{\begin{array}{l}1,n=1\\ {\sum }_{i=1}^{n-1}[gcd(i,n-i)==1],n>1\end{array}$$
$$g(n)=\sum _{d|n}f(\frac{n}{d})$$
$$G_k(n)=\{\begin{array}{l}f(g(n)),k=1\\ g(G_{k-1}(n)),k>1\wedge kmod2=0\\ f(G_{k-1}(n)),k>1\wedge kmod2=1\end{array}$$

Solution:

对于f(n)函数的处理：

$gcd(i,n-i)=gcd(i,n)$
当n>1时
$$\begin{gathered} f(n)=\sum _{i=1}^{n-1}[gcd(i,n-i)==1] \\ =\sum _{i=1}^{n-1}[gcd(i,n)==1] \\ =\phi (n) \end{gathered}$$
所以
$$f(n)=\phi (n)$$

对于g(n)函数的处理：

$$\begin{gathered} g(n)=\sum _{d|n}f(\frac{n}{d}) \\ n=1,g(1)=1 \\ n>1,g(n)=\sum _{d|n}f(\frac{n}{d}) \\ =\sum _{d|n}\phi (\frac{n}{d}) \\ =n \end{gathered}$$
所以$$g(n)=n$$

对于$G_k(n)$函数的处理：

$$\begin{gathered} G_k(n)=\{\begin{array}{l}f(g(n)),k=1\\ g(G_{k-1}(n)),k>1\wedge kmod2=0\\ f(G_{k-1}(n)),k>1\wedge kmod2=1\end{array} \\ =\{\begin{array}{l}\phi (n),k=1\\ G_{k-1}(n),k>1\wedge kmod2=0\\ \phi (G_{k-1}(n)),k>1\wedge kmod2=1\end{array} \end{gathered}$$
易得求$G_k(n)$，就是求$\lfloor \frac{k+1}{2}\rfloor$次$\phi$
并且在求$lo{g}_{2}n$次后，恒有$\phi (1)=1$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
unordered_map<ll,ll> mpsmu;
const int N=1e6;
const int mod=1e9+7;
int prime[N+5],notprime[N+5],cnt=0;
int phi[N+5];
void initPhi()
{
   
    phi[1]=1;notprime[1]=1;
    for(int i=2;i<=N;i++)
    {
   
        if(!notprime[i])
        {
   
            prime[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<cnt&&1ll*i*prime[j]<=N;j++)
        {
   
            notprime[i*prime[j]]=1;
            if(i%prime[j])phi[i*prime[j]]=phi[i]*(prime[j]-1);
            else{
   phi[i*prime[j]]=phi[i]*prime[j];break;}
        }
    }
}
int t;
ll n,k;
int main()
{
   
    initPhi();
    scanf("%d",&t);
    while(t--)
    {
   
        scanf("%lld%lld",&n,&k);
        k=(k+1)/2;
        while(k--)
        {
   
            if(n==1)break;
            if(n<=N)n=phi[n];
            else
            {
   
                ll x=n;
                for(int i=0;i<cnt;i++)
                {
   
                    int c=0;
                    while(x%prime[i]==0)x/=prime[i],c++;
                    if(c>0)n=n/prime[i]*(prime[i]-1);
                    if(x<=N&&!notprime[x]){
   n=n/x*(x-1);x=1;break;}
                    if(x==1)break;
                }
                if(x>1)n=n/x*(x-1);
            }
        }
        n=n%mod;
        printf("%lld\n",n);
    }
    return 0;
}