欧拉函数-gcd-快速幂(牛客寒假算法基础集训营1-D-小a与黄金街道)

时间:2022-10-21 04:31:43

题目描述:

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

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

输入描述:

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

输出描述:

输出一个整数表示答案

示例1:

输入:

4 2 1 1

输出:

32

说明:

初始时A=1,B=1A=1,B=1

第一个时刻如图所示,小a在11,小b在33,满足条件,此时A=1∗21=2,B=1∗23=8A=1∗21=2,B=1∗23=8

欧拉函数-gcd-快速幂(牛客寒假算法基础集训营1-D-小a与黄金街道)
 

第二个时刻小a在22,小b在22,不满足条件

欧拉函数-gcd-快速幂(牛客寒假算法基础集训营1-D-小a与黄金街道)
 

第三个时刻小a在33,小b在11,满足条件,此时A=2∗23=16,B=8∗21=16A=2∗23=16,B=8∗21=16

欧拉函数-gcd-快速幂(牛客寒假算法基础集训营1-D-小a与黄金街道)

此时游戏结束A=2∗23=16,B=8∗21=16A=2∗23=16,B=8∗21=16

A+B=32A+B=32

示例2:

输入:

5 1 1 1

输出:

2

备注:

保证3⩽n⩽108,1⩽A,B,k⩽10133⩽n⩽108,1⩽A,B,k⩽1013

解析:

若gcd (