欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-10-06 16:49:51
题目描述: 链接:https://ac.nowcoder.com/acm/contest/317/D来源:牛客网小a和小b来到了一条布满了黄金的街道上。它们想要带几块黄金回去,然而这里的城管担心他们拿走的太多,于是要求小a和小b通过做一个游戏来决定最后得到的黄金的数量。 游戏规则是这样的: 假设道路 ......

题目描述:

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

小a和小b来到了一条布满了黄金的街道上。它们想要带几块黄金回去,然而这里的城管担心他们拿走的太多,于是要求小a和小b通过做一个游戏来决定最后得到的黄金的数量。
游戏规则是这样的:
假设道路长度为nn米(左端点为00,右端点为nn),同时给出一个数kk(下面会提到kk的用法)
设小a初始时的黄金数量为aa,小b初始时的黄金数量为bb
小a从11出发走向n1n−1,小b从n1n−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会变为akx(kg)a∗kx(kg),小b的黄金数量bb会变为bky(kg)b∗ky(kg)
当小a到达n1n−1时游戏结束
小a想知道在游戏结束时a+ba+b的值
答案对