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

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

题目描述

小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

思路：

看了题目意思，很明显是欧拉函数。然后k的次幂是1到n的欧拉函数的和，有一个基本公式是

（n）*n/2.

然后用个快速幂。

代码：

#include #include #include #include #include #include #include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。