链接：https://ac.nowcoder.com/acm/contest/317/D
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

小a和小b来到了一条布满了黄金的街道上。它们想要带几块黄金回去，然而这里的城管担心他们拿走的太多，于是要求小a和小b通过做一个游戏来决定最后得到的黄金的数量。
游戏规则是这样的：
假设道路长度为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∗k^x(kg)，小b的黄金数量B会变为B∗k^y(kg)
当小a到达n−1时游戏结束
小a想知道在游戏结束时A+B的值
答案对 1e9+7 取模

输入描述:

一行四个整数 n,k,A,B

输出描述:

输出一个整数表示答案

示例1

输入

复制

4 2 1 1

输出

复制

32

说明


 

初始时A=1,B=1

第一个时刻如图所示，小a在1，小b在3，满足条件，此时A=1∗2^1=2, B=1∗2^3=8

 

第二个时刻小a在2，小b在2，不满足条件

 

第三个时刻小a在3，小b在1，满足条件，此时A=2∗2^3=16,  B=8∗2^1=16

此时游戏结束A=2∗2^3=16, B=8∗2^1=16

A+B=32

示例2

输入

复制

5 1 1 1

输出

复制

2

备注:

保证3⩽n⩽10^8, 1⩽A,B,k⩽10^13

题意：就是求A*k^x1*k^x2.....*k^xn..+B*k^y1*k^y2.......*k^yn = A*k^(x1+x2+...xn)+B*k^(y1+y2+...yn); 要求是: gcd(n,x)=1,gcd(n,y)=1;并且到达x,y位置的时间一样,最后要模1e9+7

题解：如果gcd(n,x)=1则gcd(n,n-x)=1这就保证了时间一样，而且这样找下来就是与n互质的所有数，而且这样的话，(x1+x2+...+xn)=(y1+y2+...yn)=与n互质的所有数的和，这样我们就可以想到，用欧拉函数，求所有与n互质的和；

和为sum=n*get_euler(n)/2; 这样就变成求(A*k^sum+B*k^sum)%mod；更多解释看代码：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll get_euler(ll n){ // 欧拉函数模板
    ll res=n,a=n;
    for (ll i = 2; i*i<=a;i++){
        if(a%i==0){
            res=res/i*(i-1);
            while(a%i==0) a=a/i;
        }
    }
    if(a>1) res=res/a*(a-1);
    return res;
}
ll quick(ll a,ll b,ll c){//快速幂
    ll ans=1;  
    a=a%c;
    while(b!=0){
        if(b&1) ans=(ans*a)%c;
        b>>=1;
        a=(a*a)%c;
    }
    return ans;
}
int main(){
    ll n,k,a,b;
    scanf("%lld%lld%lld%lld",&n,&k,&a,&b);
    ll sum=n*get_euler(n)/2;
    a=a*quick(k,sum,mod)%mod;//quick()用来求k^sum
    b=b*quick(k,sum,mod)%mod;
    printf("%lld\n",(a+b)%mod);
    return 0;
}