首页 > 代码库 > Codeforces Round #400 E. The Holmes Children

Codeforces Round #400 E. The Holmes Children

2024-09-06 00:00:53   216人阅读

题目链接：Codeforces Round #400 E. The Holmes Children

题意：

定义f(1)=1，f(n),n>1的值为满足x+y=n且gcd(x,y)=1的(x,y)个数；定义g(n)=Σd|n f(n/d)；定义Fk(n)满足k=1时Fk(n)=f(g(n))，k>1且k mod 2=0时Fk(n)=g(Fk-1(n))，k>1且k mod 2=1时Fk(n)=f(Fk-1(n)) 。给出n,k，求Fk(n)mod 1000000007。（1<=n,k<=10^12）

题解：

f(n)等同于求满足gcd(x,n-x)=1的x的个数，又因为gcd(x,n-x)=gcd(x,n)，所以f(n)就是phi(n)。通过观察发现g(n)=n，所以Fk(n)就是对n做(k+1)/2遍phi。每次n^0.5暴力，n=1时停止就可以了，因为n>2时，phi(n)必为偶数，偶数的phi又必然减少一半，所以复杂度大约是O(n^0.5*logn)。

以上题解转自http://www.cnblogs.com/ditoly/p/CF400.html。

其实观察出g(n)=n后，剩下的就是欧拉函数的暴力了。

技术分享 
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 
 5 const int P=1000000007;
 6 
 7 ll eular(ll n)
 8 {
 9     ll ret=1,i;
10     for(i=2;i*i<=n;i++)
11     {
12         if(n%i==0)
13         {
14             n/=i,ret*=i-1;
15             while(n%i==0)n/=i,ret*=i;
16         }
17     }
18     if(n>1)ret*=n-1;
19     return ret;
20 }
21 
22 ll f(ll n,ll k)
23 {
24     if(n==1)return 1;
25     if(k==1)return eular(n);
26     return f(eular(n),k-1);
27 }
28 
29 int main(){
30     ll n,k;
31     scanf("%I64d%I64d",&n,&k);
32     printf("%I64d\n",f(n,(k+1)/2)%P);
33     return 0;
34 }
View Code

 

Codeforces Round #400 E. The Holmes Children


联系
我们