小x的奇遇-adventure

题意：

给定函数f(n),g(n),求 $G_k(n)$
$f(n)=\begin{cases} 1,n=1\\ \sum_{i=1}^{n-1}[gcd(i,n-i)==1],n>1 \end{cases}$
$g(n)=\sum_{d|n}f(\frac{n}{d})$
$G_k(n)=\begin{cases} f(g(n)),k=1\\ g(G_{k-1}(n)),k>1 \land k\ mod\ 2=0\\ f(G_{k-1}(n)),k>1 \land k\ mod\ 2=1 \end{cases}$

Solution:

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

$g c d (i, n - i) = g c d (i, n)$
当n>1时
$f(n)=\sum_{i=1}^{n-1}[gcd(i,n-i)==1]\\ =\sum_{i=1}^{n-1}[gcd(i,n)==1]\\ =\varphi(n)$
所以
$f(n)=\varphi(n)$

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

$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}\varphi(\frac{n}{d}) \\ =n$
所以 $g (n) = n$

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

$G_k(n)=\begin{cases} f(g(n)),k=1\\ g(G_{k-1}(n)),k>1 \land k\ mod\ 2=0\\ f(G_{k-1}(n)),k>1 \land k\ mod\ 2=1 \end{cases}\\ =\begin{cases} \varphi(n),k=1\\ G_{k-1}(n),k>1 \land k\ mod\ 2=0\\ \varphi(G_{k-1}(n)),k>1 \land k\ mod\ 2=1 \end{cases}$
易得求 $G_k(n)$ ，就是求 $\lfloor\frac{k+1}{2}\rfloor$ 次 $\varphi$
并且在求 $log_2n$ 次后，恒有 $\varphi(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;
}

小x的奇遇-adventure