可爱风格网站,表情网站源码,中国企业网站建设,湖北网站建设电话链接#xff1a;https://ac.nowcoder.com/acm/contest/317/D 来源#xff1a;牛客网 题目描述 小a和小b来到了一条布满了黄金的街道上。它们想要带几块黄金回去#xff0c;然而这里的城管担心他们拿走的太多#xff0c;于是要求小a和小b通过做一个游戏来决定最后得到的黄金… 链接https://ac.nowcoder.com/acm/contest/317/D 来源牛客网 题目描述 小a和小b来到了一条布满了黄金的街道上。它们想要带几块黄金回去然而这里的城管担心他们拿走的太多于是要求小a和小b通过做一个游戏来决定最后得到的黄金的数量。 游戏规则是这样的假设道路长度为n米(左端点为0右端点为n)同时给出一个数k(下面会提到k的用法)设小a初始时的黄金数量为A小b初始时的黄金数量为B小a从1出发走向n−1小b从n−1出发走向1两人的速度均为1m/s 假设某一时刻(必须为整数)小a的位置为x,小b的位置为y,若gcd(n,x)1且gcd(n,y)1那么小a的黄金数量会变为A∗kx(kg),小b的黄金数量,B会变为B∗ky(kg)当小a到达n−1时游戏结束,小a想知道在游戏结束时AB的值,答案对1097取模输入描述: 一行四个整数n,k,A,B输出描述: 输出一个整数表示答案示例1 输入 4 2 1 1 输出 32示例2 输入 5 1 1 1 输出 2备注:3⩽n⩽108,1⩽A,B,k⩽1013 示例1说明 官方题解 #includecstdio
#includecstdlib
#includeiostream
#includecmath
#includecstring
#includealgorithm
#includestring
#includequeue
#includevector
#define pi 3.1415926
#define mod 1000000007
using namespace std;//typedef pairint,int Node;
typedef long long LL;
const int Max_n10005;
int prime[Max_n],is_prime[Max_n];
int j;void GetPrime(){for(int i2;iMax_n;i) is_prime[i]1;for(int i2;isqrt(Max_n);i){if(is_prime[i]){for(int ji*i;jMax_n;ji)is_prime[j]0;}}j1;for(int i2;iMax_n;i)if(is_prime[i])prime[j]i;
}
//欧拉函数
LL phi(LL n){LL ans1;for(int i1;ij;i){if(n%prime[i]0){//存在素因子int num0;//当前素因子的个数while(n%prime[i]0){num;n/prime[i];}for(int k1;knum;k) ans(ans*prime[i])%mod;ans(ans*(prime[i]-1))%mod;//此处和上面注意这里是prime[i]if(n1) break;}}if(n1) ansn-1;//n是素数return ans;
}LL Qpow(LL a,LL b){LL ans1;LL resa%mod;while(b){if(b1) ans(ans*res)%mod;res(res*res)%mod;b1;}return ans;
}
int main(){GetPrime();//这里不要忘记LL n,k,a,b;scanf(%lld%lld%lld%lld,n,k,a,b);LL ans((ab)%mod*Qpow(k,n*phi(n)/2));//模运算规则((a^b)%p)((a%p)^b)%p printf(%lld,ans%mod);return 0;
}模运算规则 (a±b)%p(a%p±b%p)%p (a * b)%p(a%p * b%p)%p ab%p(a%p)b%p 转载于:https://www.cnblogs.com/zut-syp/p/10543689.html
