描述

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

输入

一行四个整数n,k,a,b

输出

输出一个整数表示答案

样例

Input

4 2 1 1

5 1 1 1

Output

32

2

思路

求出1到n中与n互质的数的和sum，最后答案为k^sum*(A+B)

sum=phi(n)*n/2,phi(n)为;

当sum过大时（此处不用），需要使用欧拉降幂，即x^sum%Mod=x^(sum%phi(Mod)+phi(Mod)) %Mod;

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

#include
         
           #define INIT(a,b) memset(a,b,sizeof(a)) #define LL long long int using namespace std; const int MAX=0x7fffffff; const int MIN=-0x7fffffff; const int INF=0x3f3f3f3f; const int Mod=1e9+7; const int MaxN=1e7+7; const LL c=1e9+7; LL phi(LL n){
        //欧拉函数      LL i,rea=n;      for(i=2;i*i<=n;i++){
                 if(n%i==0){
                     rea=rea-rea/i;              while(n%i==0) n/=i;           }      }      if(n>1) rea=rea-rea/n;      return rea; } LL PowerMod(LL a, LL b) {
            LL ans = 1;     a = a % c;     while(b>0) {
                if(b % 2 == 1)         ans = (ans * a) % c;         b = b/2;         a = (a * a) % c;     }     return ans; } int main(){
            //freopen("1.in","r",stdin);     //freopen("1.out","w",stdout);     LL n,k,a,b; 	scanf("%lld %lld %lld %lld",&n,&k,&a,&b); 	LL sum=n*phi(n)/2; 	LL tem=phi(c); 	sum=sum%tem+tem; 	LL res=PowerMod(k,sum)*(a+b)%c; 	printf("%lld\n",res);     return 0; }

转载地址：https://blog.csdn.net/cpongo3/article/details/89334385 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

描述

输入

输出

样例

思路

Code

发表评论

最新留言

关于作者

推荐文章