企业网站备案怎么做,佛山网站设计资讯,产品推广方案模板,微信网站公司题干#xff1a;
链接#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通过做一个游戏来决定最后得到的黄金的数量。 游戏规则是这样的 假设道路长度为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想知道在游戏结束时ABAB的值 答案对10971097取模
输入描述:
一行四个整数n,k,A,Bn,k,A,B
输出描述:
输出一个整数表示答案
示例1
输入
复制
4 2 1 1
输出
复制
32
说明 初始时A1,B1A1,B1
第一个时刻如图所示小a在11小b在33满足条件此时A1∗212,B1∗238A1∗212,B1∗238 第二个时刻小a在22小b在22不满足条件 第三个时刻小a在33小b在11满足条件此时A2∗2316,B8∗2116A2∗2316,B8∗2116 此时游戏结束A2∗2316,B8∗2116A2∗2316,B8∗2116
AB32AB32
示例2
输入
复制
5 1 1 1
输出
复制
2
备注: 保证3⩽n⩽108,1⩽A,B,k⩽10133⩽n⩽108,1⩽A,B,k⩽1013
解题报告 这题数据减弱成1e8了这样就可以暴力了、、但是原先这题是1e13需要用欧拉函数相关知识。 首先知道如果gcd(x,n) 1 则gcd(n-x,n) 1.证明方法很多种这里给出两种第一种假设gcd(n-x,n) d ( d ! 1 ) 则和第一个条件有矛盾第二种因为gcd(x,n) 1 所以gcd(-x,n) 1所以gcd(n-x,n) 1即gcd(a,b)1则gcd(ab,b)1。而这题中我们找到了一个比较好的条件就是xyn所以条件可以化简成gcd(x,n) 1 就行了。
求出可以推出因为欧拉函数都是两两配对的除了2这个数而2带进去也是可以整除的所以等号右侧一定可以除尽最终答案就是
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
const ll mod 1e97;
ll qpow(ll a,ll k) {ll res 1;while(k) {if(k1) res (res*a)%mod;a (a*a)%mod;k1;}return res;
}
ll E(ll n) {ll res n;for(ll p 2; p*pn; p) {if(n%p0) {res res/p*(p-1);while(n%p0) n/p;}}if(n1) res res/n*(n-1);return res;
}
int main()
{ll n,k,a,b;
// coutE(4)endl;cinnkab;cout (ab) * qpow(k,E(n)*n/2)%mod endl;return 0 ;}
