题目链接：https://ac.nowcoder.com/acm/contest/3***>
题目大意：给你四个整数：n， k, A, B。
小a从1走到n-1， 小b从n-1走到1。速度都为1m/s。若gcd(n,x)=1且gcd(n,y)=1，那么小a的黄金数量A会变为A∗ k^x(kg)。小b的黄金数量BB会变为B∗k ^ y(kg)当小a到达n−1时游戏结束。小a想知道在游戏结束时A+B的值。
答案对10^9+7取模

思路：其实很好想答案就是：(A+B)*k^(x)
x是所有gcd(i, n)==1&&gcd(n-i, n)==1的i+(n-i)的和。可能是好久没有做数论题了，当时还想暴力，10^8/2。后来突然发现这个跟欧拉函数有点关系。欧拉函数euler(n)：等于小于n的所有与n互质的数的个数。如果gcd(i, n)==1的时候gcd(n-i, n)==1也满足就可以了。百度一下，这个结论是成立的。

所以：(A+B)*k^( euler(n) /2 * n)，应该不会T。不过还是用了快速幂。

思考：这次应该是在牛客网打的最好的一次了吧。最后排名31。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
//#define p1 first
//#define p2 second
//memset(a, 0, sizeof(a));
//stack堆栈 queue队列 priority_queue优先队列
//vector向量 multiset平衡二叉树 deque双端队列
//pair{T1 first;T2 second;} greater<T>
//unordered_map 哈希map

set<int> s;

const int mod=1e9+7;

//快速乘法(a*b)%mod
LL quick_mul(LL a, LL b)
{
    LL ans=0;
    while(b)
    {
        if(b&1)
            ans=(ans+a)%mod;
        a=(a+a)%mod;

        b>>=1;
    }
    return ans;
}

//快速幂(a^b)%mod
LL quick_pow(LL a, LL b)
{
    LL ans=1;
    while(b)
    {
        if(b&1)
            ans=quick_mul(ans, a);
        a=quick_mul(a, a);

        b>>=1;
    }
    return ans;
}

LL euler(LL n)
{
    LL res=n;
    for(LL i=2;i*i<=n;i++)
    {
        if(n%i==0)//第一次找到的必为素因子
            res=res/i*(i-1);
        while(n%i==0)//把该素因子全部约掉
            n/=i;
    }
    if(n>1)
        res=res/n*(n-1);

    return res;
}

int main()
{
    int n, k, A, B, ans=0;
    scanf("%d%d%d%d",&n,&k,&A,&B);
    ans=euler((LL)n);
    ans=(ans/2)*n;
    printf("%lld\n",((A+B)*quick_pow(k, ans))%mod);

    return 0;

}