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.
InputA 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.
OutputOutput 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,证明过程比较复杂,你看这个博客,这个可以当做结论,牢牢得记住就好了。
证明在这:
最后接下来就是求解了,这个式子展开可以得到,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;
}
本文发布于:2024-01-27 23:01:44,感谢您对本站的认可!
本文链接:https://www.4u4v.net/it/17063677043169.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
留言与评论(共有 0 条评论) |