校内测试考了这道题,当时按照题目背景瞎搞了搞,把样例水过了,结果爆零/kk
开始还以为正解要从题目背景中推出来,搞了一个多小时。考完发现背景和题目没什么关系啊!再也不看题目背景了
首先题面用粗体强调了:(e_1) 与 (e_2) 互素。也就是说,有整数 (s,t),满足:
[s*e_1+t*e_2= {
m{gcd}}(e_1,e_2)=1
]
突破口一定是这个式子。
再看题目中 (m) 是以 (m^{e_1},m^{e_2}) 出现的,上面的那个式子可能要放到指数上。
这个 ("1") 就很巧妙啊,可以代换到很多地方,比如代进指数的位子上去,并不影响原值。
则答案
[m equiv m^1 equiv m^{s*e_1+t*e_2} ({
m {mod}} N)
]
这个式子又可以写成:
[m equiv (m^{e_1})^s(m^{e_2})^t ({
m {mod}} N)
]
把题中所给的 (c_1,c_2) 代入得:
[m equiv c_1^sc_2^t ({
m {mod}} N)
]
(s,t)显然可以用扩展欧几里得算法求得,所以答案即为 (c_1^sc_2^t { m {mod}} N)。
极大数求幂显然要用到快速幂,而 (s,t) 可能为负数,快速幂就没法求了。所以我们需要把指数转变为正数求解。
运用所学初中知识:
[c^x=(c^{-1})^{-x}
]
使用扩展欧几里得算法求解逆元即可。
另外,快速幂和计算 (c_1^sc_2^t) 时要用龟速乘,否则第二个点爆 long long
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define lxl long long
#define debug(x) printf("debug : %lld
", x)
using namespace std;
inline lxl fti(lxl a,lxl b,lxl p)
{
lxl ans=0;
while(b>0)
{
if(b&1) ans=(ans+a)%p;
a=(a+a)%p;
b>>=1;
}
return ans;
}
inline lxl fmi(lxl a,lxl b,lxl p)
{
lxl ans=1;
a%=p;
while(b>0)
{
if(b&1) ans=fti(ans,a,p);
a=fti(a,a,p);
b>>=1;
}
return ans%p;
}
inline lxl exgcd(lxl a,lxl b,lxl &x,lxl &y)
{
if(!b) {x=1,y=0;return a;}
lxl k=exgcd(b,a%b,x,y);
lxl z=x;x=y,y=z-a/b*y;
return k;
}
inline lxl inv(lxl a,lxl b)
{
lxl x,y;
lxl g=exgcd(a,b,x,y);
return g==1?(x%b+b)%b:-1;
}
lxl c1,c2,e1,e2,N;
int main()
{
//freopen("P5451.in","r",stdin);
int t;scanf("%d",&t);
while(t--)
{
scanf("%lld%lld%lld%lld%lld",&c1,&c2,&e1,&e2,&N);
lxl s,t,g=exgcd(e1,e2,s,t);
if(s<0) c1=inv(c1,N),s=-s;
if(t<0) c2=inv(c2,N),t=-t;
printf("%lld
",fti(fmi(c1,s,N),fmi(c2,t,N),N));
}
return 0;
}