COGS2531. [HZOI 2016]函数的美 打表+欧拉函数

题目：http://cogs.pw/cogs/problem/problem.php?pid=2533

这道题考察打表观察规律。

发现对f的定义实际是递归式的

f(n,k) = f(0,f(n-1,k))

f(0,k) = balabalabalabala

所以，实际上的f(n,k)是这么个东西

f(0,(0,(0,(0,(0,(0,(0,(0,k))))))))

直接递归求解并打出表来，我们可以发现这样的事实

f(0,k) = k+1

所以有f(n,k) = n + k + 1;

所以题目就转化为了求n+k+1的欧拉函数，直接O(sqrt(n))解决

严谨的数学证明：

但是这道题其实本人认为最恰当的做法就是打表观察规律

仔仔细细的证明推式子有些得不偿失

 #include <cmath>

 #include <queue>

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef long long ll;

 inline void read(ll &x){

     x=;char ch;bool flag = false;

     while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

     while(x=*x+ch-'',ch=getchar(),ch>'!');if(flag) x=-x;

 }

 inline ll cat_max(const ll &a,const ll &b){return a>b ? a:b;}

 inline ll cat_min(const ll &a,const ll &b){return a<b ? a:b;}

 inline ll phi(ll x){

     ll ret = x;

     for(ll i=;i*i<=x;++i){

         if(x % i == ){

             ret /= i;ret *= (i-);

             while(x % i == ) x /= i;

         }

     }

     if(x^) ret /= x,ret *= (x-);

     return ret;

 }

 int main(){

     freopen("skyfuc.in","r",stdin);

     freopen("skyfuc.out","w",stdout);

     ll n,x;

     while(scanf("%lld%lld",&n,&x) != EOF)

         printf("%lld\n",phi(n+x+));

     getchar();getchar();

     return ;

 }