2021牛客寒假算法基础集训营3 A模数的世界
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了2021牛客寒假算法基础集训营3 A模数的世界,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1028字,纯文字阅读大概需要2分钟。
内容图文
![2021牛客寒假算法基础集训营3 A模数的世界](/upload/InfoBanner/zyjiaocheng/607/8ab18ff84e4e461f9cde6266c0a74c7e.jpg)
题意如图:
思路:
1 (a=0&b=0情况下特判输出0)
2 首先发现g必定是p-1,证明如下:
p%(p-1)=1;
a%(p-1)=a;
a+k * p % (p-1) =( a%p + k * p%(p-1) ) %(p-1)
a+k * p % (p-1) =( a+ k * 1 ) %(p-1)
a+k * p % (p-1) =( a+ k ) %(p-1)
所以a+kp可以是(p-1)的倍数,
同理b+kp可以是(p-1)的倍数,
所以gcd(a+k1p,b+k2p) 是 (p-1)的倍数
令
a+k1 * p=t1*(p-1),
b+k2 * p=t2*(p-1)
当t1,t2互质时,gcd(a+k1*p,b+k2 *p)=p-1
答案为最大
发现 t2 * (p-1) + p * (p-1) 时仍是(p-1)的倍数
此时t2 * (p-1) + p * (p-1) =(t2+p) * (p-1)
所以可以通过给t2一直加p的形式让t2和t1互质
此时答案可解
代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+15;
typedef long long ll;
ll gcd(ll a,ll b)
{
if(b==0)
return a;
return gcd(b,a%b);
}
int main()
{
ll t,a,b,p;
cin>>t;
while(t--)
{
scanf("%lld%lld%lld",&a,&b,&p);
if(a==0&&b==0)
{
printf("0 0 0\n");
continue;
}
ll op1=(p-1-a)*p+a;
ll op2=(p-1-b)*p+b;
op1=op1/(p-1);
op2=op2/(p-1);
ll ok=gcd(op1,op2);
if(ok!=1)
{
while(op2%ok==0)
{
op2+=p;
}
while(gcd(op1,op2)!=1)
{
op2+=p;
}
}
printf("%lld %lld %lld\n",p-1,op1*(p-1),op2*(p-1));
}
return 0;
}
内容总结
以上是互联网集市为您收集整理的2021牛客寒假算法基础集训营3 A模数的世界全部内容,希望文章能够帮你解决2021牛客寒假算法基础集训营3 A模数的世界所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。