CodeForces 1314F Bad Croptography

CodeForces 1314F Bad Croptography

https://codeforces.com/contest/1314/problem/F

给出 (a,b) ,在nim积的意义下求一个小于 (2^{64}) 次方的数 (x) 满足

[a^x = b ]

(0 le a,b < 2^{64})

Tutorial

在剩余系中求对数的方法,我们采用BSGS在 (O(sqrt m)) 的时间求解.然而这无法直接套用在这道题上.

(a) 的乘法群的大小为 (F=2^{64}-1) .

观察发现 (F=3 imes 5 imes 17 imes 257 imes 641 imes 65537 imes 6700417) .其中每个数都是一个不大的质数.

所以考虑求出 (x) 对于每个上列质数的余数后用中国剩余定理合并.

加入我们要对于 (p) 求解,那么

[a^{k cdot p + y} = b \ a^{kF+y cdot frac Fp} = b^{frac Fp} ]

其中 (a^F=1)

[a^{y cdot frac Fp} = b^{frac Fp} \ (a^{frac Fp})^y = b^{frac Fp} ]

令 (a' = a^{frac Fp},b'=b^{frac Fp}) 那么我们要求的就是

[(a')^y=b' ]

其中 (y in [0,p)) ,所以可以用BSGS的思想求解.

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#define inver_nim(a) power_nim(a,F-1)
#define inver(a,mod) power(a,mod-2,mod)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const ull F=~0ull;
static int p[]={3,5,17,257,641,65537,6700417};
int T;
ull a,b;
int x[7];
ull nim[256][256];
ull f(ull x,ull y,int len=32) {
    if(x==0||y==0) return 0;
    if(x==1||y==1) return x*y;
    if(len<=4&&nim[x][y]) return nim[x][y];
    ull xa=x>>len,xb=x^(xa<<len),ya=y>>len,yb=y^(ya<<len);
    ull a=f(xb,yb,len>>1),b=f(xa^xb,ya^yb,len>>1),c=f(xa,ya,len>>1),d=f(c,1ull<<len-1,len>>1);
    ull re=((b^a)<<len)^a^d;
    if(len<=4) nim[x][y]=re;
//	debug("%llu %llu %llu
",x,y,re);
    return re;
}
ull power_nim(ull x,ull y) {
    ull re=1;
    while(y) {
        if(y&1) re=f(re,x);
        x=f(x,x);
        y>>=1;
    }
    return re;
}
ll power(ll x,ll y,int mod) {
    ll re=1;
    while(y) {  
        if(y&1) re=re*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return re;
}
ull add(ull x,ull y) {return x>=F-y?x+y-F:x+y;}
ull mul(ull x,ull y) {
    ull re=0;
    while(y) {
        if(y&1) re=add(re,x);
        x=add(x,x);
        y>>=1;
    }
    return re;
}
namespace Hash {
    const int mod=2e3+7;
    int head[mod];
    struct node {
        int val,nex; ull key;
        node(int val=0,int nex=0,ull key=0):val(val),nex(nex),key(key){}
    };
    vector<node> G;
    int find(ull k) {
        int z=k%mod;
        for(int i=head[z];~i;i=G[i].nex) {
            if(G[i].key==k) return G[i].val;
        }
        return -1;
    }
    void insert(int v,ull k) {
        if(find(k)!=-1) return;
        int z=k%mod;
        G.push_back(node(v,head[z],k)),head[z]=G.size()-1;
    }
    void init() {
        memset(head,-1,sizeof(head));
        G.clear();
    }
}
ull BSGS(ull a,ull b,int p,int &re) {
//     debug("%llu %llu %d
",a,b,p);
    if(a==1&&b==1) {re=0; return 1;}
    Hash::init();
    int m=ceil(sqrt(p));
    ull t1=1,t2=1;
    for(int j=0;j<m;++j) {
        // debug("%d %llu
",j,t1);
        Hash::insert(j,t1);
        t1=f(t1,a);
    }
    t1=inver_nim(t1);
    // debug("%lld
",t1);
    for(int i=0;i<m;++i) {
        // debug("%d %llu
",i,f(b,t2));
        int j=Hash::find(f(b,t2));
        if(j!=-1) {re=i*m+j; return 1;}
        t2=f(t2,t1);
    }
    return 0;
}
int main() {
//    freopen("CF.in","r",stdin);
//    freopen("CF.out","w",stdout);
    scanf("%d",&T);
    while(T--) {
        scanf("%llu%llu",&a,&b);
        bool ok=1;
        for(int i=0;i<7;++i) {
            if(!BSGS(power_nim(a,F/p[i]),power_nim(b,F/p[i]),p[i],x[i])) {ok=0; break;}
            // debug("%d %d
",i,x[i]);
        }
        if(!ok) {puts("-1"); continue;}
        ull an=0;
        for(int i=0;i<7;++i) {
            an=add(an,mul((ull)x[i]*inver(F/p[i]%p[i],p[i]),F/p[i]));
        }
        printf("%llu
",an);
    }
    return 0;
}