【codeforces 776E】The Holmes Children

【题目链接】:http://codeforces.com/contest/776/problem/E

【题意】



f(n)是小于n的不同整数对(x,y)这里x+y==n且gcd(x,y)==1的个数;

g(n)是n的所有因子的f值的和;

然后让你求一个递推式

【题解】



x的欧拉函数为phi(x)

则f(n)=phi(n);

欧拉函数的定义是,小于这个值且与这个值互质的数的个数->phi(n);

可以证明每一个与n互质的数x对应了一个整数对(x,y)且x+y==n且gcd(x,y)==1;

然后有个可以记住的东西;

n的所有因子的欧拉函数的和为这个数本身;

所以

f(n)=phi(n);

g(n)=n

根据递推式容易求出fk(n);

做(k+1)/2次欧拉函数就好;

偶数次只是传值;奇数次在计算；

在数论中，对于正整数N,少于或等于N ([1,N]),且与N互质的正整数(包括1)的个数，记作φ(n)。

/*

    在数论中，对于正整数N,少于或等于N ([1,N]),且与N互质的正整数(包括1)的个数，记作φ(n)。

     φ函数的值：

    φ(x)=x(1-1/p(1))(1-1/p(2))(1-1/p(3))(1-1/p(4))…..(1-1/p(n)) 其中p(1),p(2)…p(n)为x

的所有质因数;x是正整数; φ(1)=1(唯一和1互质的数，且小于等于1)。注意：每种质因数只有一个。

     例如:

         φ(10)=10×(1-1/2)×(1-1/5)=4;

         1 3 7 9

         φ(30)=30×(1-1/2)×(1-1/3)×(1-1/5)=8;

         φ(49)=49×(1-1/7)=42;

*/

【Number Of WA】



1



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define ps push_back

#define fi first

#define se second

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%lld",&x)

#define ref(x) scanf("%lf",&x)

typedef pair<int, int> pii;

typedef pair<LL, LL> pll;

const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };

const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };

const double pi = acos(-1.0);

const int N = 110;

LL n, k,num;

LL MOD = 1e9 + 7;

LL oula(LL x)

{

    LL rest = x;

    for (LL i = 2; i*i <= x;i++)

        if (x%i == 0)

        {

            rest -= rest / i;

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

        }

    if (x > 1)

        rest -= rest / x;

    return rest;

}

int main()

{

    //freopen("F:\\rush.txt", "r", stdin);

    rel(n), rel(k);

    num = (k + 1) / 2;

    while (num-- && n > 1)

        n = oula(n);

    cout << n%MOD << endl;

    //printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);

    return 0;

}