2021牛客寒假算法基础集训营3 A模数的世界

2021牛客寒假算法基础集训营3   A模数的世界
2021牛客寒假算法基础集训营3   A模数的世界

题意如图:

思路:
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+k
p可以是(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;
}


上一篇:C语言学习笔记01


下一篇:关于 糖果传递 一题的思路+代码