codeforces 776E - The Holmes Children

The Holmes children are fighting over who amongst them is the cleverest.

Mycroft asked Sherlock and Eurus to find value of f(n), where f(1) = 1 and for n ≥ 2, f(n) is the number of distinct ordered positive integer pairs (x, y) that satisfy x + y = n and gcd(x, y) = 1. The integer gcd(a, b) is the greatest common divisor of a and b.

Sherlock said that solving this was child's play and asked Mycroft to instead get the value of . Summation is done over all positive integers d that divide n.

Eurus was quietly observing all this and finally came up with her problem to astonish both Sherlock and Mycroft.

She defined a k-composite function Fk(n) recursively as follows:

She wants them to tell the value of Fk(n) modulo 1000000007.

A single line of input contains two space separated integers n (1 ≤ n ≤ 1012) and k (1 ≤ k ≤ 1012) indicating that Eurus asks Sherlock and Mycroft to find the value of Fk(n) modulo 1000000007.

Output a single integer — the value of Fk(n) modulo 1000000007.

首先先是建议同学们先找下资料看下什么是欧拉函数，以及欧拉函数的高效解法。

然后先看f(n)函数，x+y==n,gcd(x, y)==1可以得出gcd(x, n)==1;证明如下：这边用反证法：假设gcd(n, x)!=1;则另n=a*k;x=b*k;y=(a-b)*k,明显的gcd(x, y)!=1,与已知的矛盾。及f(n)就是等于欧拉函数值。

然后就是g(n)函数，是n的因子的欧拉值之和，g(n)==n,证明过程比较复杂，你看这个博客，这个可以当做结论，牢牢得记住就好了。

证明在这：http://blog.csdn.net/adjky/article/details/61198817

最后接下来就是求解了，这个式子展开可以得到，f(f(......f(f(n)))),总共嵌套(k+1)/2次，计算的时候是从里面往外面算，很快就变成1了，然后f(1)一直是1，所以当算出为1是可以当做循环的终止条件。

AC代码：

#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
typedef long long int ll;
ll phi(ll t) {//计算欧拉函数值 ll k=(ll)sqrt(t);while(k*k<=t){k++;}k--;ll ans=t;for(ll i=2; i<=k; i++){if(t%i==0){ans=ans/i*(i-1);while(t%i==0){t=t/i;}}}if(t>1)ans=ans/t*(t-1); return ans;
}
int main(){ll i, j, k, n;cin>>n>>k;k=(k+1)/2;while((k--)&&n>1){n=phi(n);}cout<<(n%1000000007);return 0;	
}