小a与黄金街道(欧拉函数)

描述

小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<bits/stdc++.h>
#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;
}
Donate comment here