一：知识点

欧拉函数的定义:

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

　    　

欧拉函数的延伸:

　　小于或等于n的数中，与n互质的数的总和为：φ(x) * x / 2  (n>1)。

（如果mod是质数，那么φ（mod）= mod-1）

欧拉函数φ(x)模板：

ll Euler(int n)//即求φ(x){    ll ret=n;    for(int i=2;i<=sqrt(n);i++)     if(n%i==0)      {        ret=ret/i*(i-1);//先进行除法防止溢出(ret=ret*(1-1/p(i)))        while(n%i==0)          n/=i;     }    if(n>1)          ret=ret/n*(n-1);        return ret;}

：

　　蒙哥马利(Montgomery)幂模运算是快速计算a^b%k的一种算法，是RSA加密算法的核心之一。

算法模板：

ll Montgomery(ll base,ll exp){    ll res = 1;    while(exp)    {        if ( exp&1 )            res = (res*base) % mod;        exp >>= 1;        base = (base*base) % mod;    }    return res;}

：()

　　实用：若gcd(n,i) == 1,那么gcd(n,n-i)==1

/*************************************************************************************************************************************/

二：牛客例题：

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32768K，其他语言65536K

64bit IO Format: %lld

题目描述 

小a和小b来到了一条布满了黄金的街道上。它们想要带几块黄金回去，然而这里的城管担心他们拿走的太多，于是要求小a和小b通过做一个游戏来决定最后得到的黄金的数量。

游戏规则是这样的：

假设道路长度为

$\mathrm{n米(左端点为0，右端点为n)，同时给出一个数k(下面会提到k的用法)设小a初始时的黄金数量为A，小b初始时的黄金数量为B小a从1出发走向n-1，小b从n-1出发走向1，两人的速度均为1m/s假设某一时刻(必须为整数)小a的位置为x，小b的位置为y，若gcd(n,x)=1且gcd(n,y)=1，那么小a的黄金数量A会变为A\ast k^x(kg)，小b的黄金数量B会变为B\ast k^y(kg)当小a到达n-1时游戏结束小a想知道在游戏结束时A}$