牛客网 小a与黄金街道

链接：

https://ac.nowcoder.com/acm/contest/317/D

来源：牛客网

题目描述

小a和小b来到了一条布满了黄金的街道上。它们想要带几块黄金回去，然而这里的城管担心他们拿走的太多，于是要求小a和小b通过做一个游戏来决定最后得到的黄金的数量。
游戏规则是这样的：
假设道路长度为nnn米(左端点为000，右端点为nnn)，同时给出一个数kkk(下面会提到kkk的用法)
设小a初始时的黄金数量为AAA，小b初始时的黄金数量为BBB
小a从111出发走向n−1n - 1n−1，小b从n−1n - 1n−1出发走向111，两人的速度均为1m/s1m/s1m/s
假设某一时刻(必须为整数)小a的位置为xxx，小b的位置为yyy，若gcd(n,x)=1gcd(n,x) = 1gcd(n,x)=1且gcd(n,y)=1gcd(n,y) = 1gcd(n,y)=1，那么小a的黄金数量AAA会变为A∗kx(kg)A k^x(kg)A∗kx(kg)，小b的黄金数量BBB会变为B∗ky(kg)B k^y(kg)B∗ky(kg)
当小a到达n−1n - 1n−1时游戏结束
小a想知道在游戏结束时A+BA+BA+B的值
答案对109+710^9 + 7109+7取模

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long int
const int mod = 1e9+7;
ll gcd(ll x,ll y){
    if(y==0) return x;
    else return(gcd(y,x%y));
}
ll pow(ll x,ll n,ll mod)
{
    ll res=1;
    while(n>0)
    {
       if(n%2==1)    
       {
            res=res*x;
            res=res%mod;
       }
       x=x*x;
       x=x%mod;
       n>>=1;
    }
    return res;    
}
int oula(int n)
{
    int rea=n;
    for(int i=2; i<=n; i++)
        if(n%i==0)//第一次找到的必为素因子
        {
            rea=rea-rea/i;
            do
                n/=i;//把该素因子全部约掉
            while(n%i==0);
        }
    return rea;
}
int main()
{
    ll n,k,A,B;
    while(cin>>n>>k>>A>>B)
    {
        ll pa=1,pb=1,sum;
        pa=A;
        pb=B;
        ll cnt=oula(n)/2;
        pa=A*pow(k,n*cnt,mod);
        pb=B*pow(k,n*cnt,mod);
        sum=(pa+pb)%mod;
        cout<<sum<<endl;
    }
    return 0;
}