526互联

AtCoder Regular Contest 158 D - Equation

发布时间 2023-04-04 21:43:41作者: sz[sz]

题目链接
原本看着式子直接晕了，觉得是高深的硬核数论，于是放弃（然后E也没想出来，sad）

关键的思路在于，考虑构造由(a,b,c)->(ta,tb,tc)这样的求解方式。

在看到这个做法后，会发现它很好地利用了题目齐次的性质；至于如何由齐次式想到这个做法，可能需要足够的天赋或者经验吧（悲）

化简后得到\(At\equiv B(\mod p)\)，那么只要A和B不为0 ，就可以得到一个非0的t，进而得到解！即要求得到一组(a,b,c)，满足在模p下：
image
（因为p是质数，故乘积为0等价于各个因式的并）

而题目又要求\(1\le a<b<c\le p-1\)，故很难直接构造出(a,b,c)，使得对于任意的p成立。
但又觉得在确定p的情况下，满足条件的三元组应该很多，所以考虑随机化；只需要证明随机一次不合法的概率有一个小于1的上界即可。
由于不知道各个因式的独立性如何，故考虑最弱的概率关系，即\(并\le和\)，考虑令每个式子均摊，只需证明:对任意整数k，随机一组(a,b,c)，\(a^k+b^k+c^k=0\)的概率小于\(1/4\)。三项单独考虑，先把\(a,b,c\)分别转成原根对应的次幂，那么每项的结果就是在长度\(p-1\)的环上每次走\(k\)步，共有\(d=\frac{p-1}{gcd(p-1,k)}\)种取值，根据\(d\)的大小分讨即可证明。

点击查看代码 
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(time(0));
int P;
inline int fpw(int a,int x){
    int s=1;
    for(;x;x>>=1,a=1ll*a*a%P) if(x&1) s=1ll*s*a%P;
    return s;
}
int n,a,b,c;
void inc(int& x,int y){
    x+=y;
    if(x>=P) x-=P;
    if(x<0) x+=P;
}
int sum(int x,int y){
    x+=y;
    if(x>=P) x-=P;
    if(x<0) x+=P;
    return x;
}
void mul(int& x,int y){
    x=1ll*x*y%P;
}
int prd(int x,int y){
    return 1ll*x*y%P;
}
void Rand(){
    unsigned int M=P-1;
    a=rnd()%M+1;
    b=rnd()%M+1;
    c=rnd()%M+1;
}
int s0,s[4];
bool chk(){
    if(a==b || b==c || a==c) return 0;
    s0=sum(a,sum(b,c));
    if(!s0) return 0;
    for(int i=1;i<=3;i++){
        int pw=1ll*n*i%(P-1);
        s[i]=sum( fpw(a,pw),sum(fpw(b,pw),fpw(c,pw)) );
        if(!s[i]) return 0;
    }
    //cout<<prd(s0,prd(s[1],s[2]))<<" "<<s[3]<<endl;
    return 1;
}
int ans[4];
void work(){
    scanf("%d%d",&n,&P);
    Rand();
    while(!chk()) Rand();
    //puts("!");
    int t=prd(s[3],fpw(s0,P-2));
    for(int i=1;i<=2;i++) mul(t,fpw(s[i],P-2));
    mul(a,t); mul(b,t); mul(c,t);
    //chk();
    //cout<<prd(s0,prd(s[1],s[2]))<<" "<<s[3]<<endl;
    ans[1]=a; ans[2]=b; ans[3]=c;
    sort(ans+1,ans+4);
    printf("%d %d %d\n",ans[1],ans[2],ans[3]);
}
int main() {
    int T; cin>>T;
    while(T--) work();
    return 0;
}