【BZOJ 2995】同余方程

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2995
数据生成器:http://paste.ubuntu.com/23021720/

拓展BSGS板题

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long
using namespace std;

const double EPS = 1e-3;
const int MAXN = 100000;

int a,b,c;

namespace Hash{
	const int MOD = 99971;
	int head[MAXN],nxt[MAXN],val[MAXN],data[MAXN],T;
	
	inline void init(){memset(head,0,sizeof(head)); T=0;}
	
	inline void insert(int v, int d) {
		nxt[++T] = head[v%MOD];
		val[T] = v; data[T] = d; 
		head[v%MOD] = T;
	}
	
	inline int query(int v){
		for (int i=head[v%MOD];i;i=nxt[i]) 
			if (val[i] == v) return data[i];
		return -1;
	}
};

inline int pow(int w, int t, int p){
	int ret = 1;
	while (t) {
		if (t & 1) ret  = (LL)ret*w % p;
		w = (LL)w*w % p; t >>= 1;
	} 
	return ret;
}

int GCD(int a, int b) {return b?GCD(b,a%b):a;}

void EX_GCD(int a, int b, LL &x, LL &y) {
	if (!b) x = 1, y = 0;
	else EX_GCD(b,a%b,y,x), y -= a/b*x;
}

inline int EX_GCD(int a, int b, int pur){
	LL ret,tmp; EX_GCD(a,b,ret,tmp);
	return (ret*pur%b+b) % b; 
}

inline void BSGS(){
	int cnt = 0,tmp,sta=1,sld[32],A=a,B=b,C=c; a %= c; b %= c; 
	while ((tmp=GCD(a,c)) > 1)
		if (b % tmp) {printf("No Solution\n"); return;}  
		else sld[++cnt] = a / tmp, b /= tmp, c /= tmp;  
	for (int i=0;i<=cnt;i++) if (pow(A,i,C) == B%C) {printf("%d\n",i); return;} 
	for (int i=1;i<=cnt;i++) sta = (LL)sta*sld[i]%c;
	
	Hash::init(); 
	int lim = int(ceil(sqrt(c)) + EPS);
	for (int i=0,w=1;i<=lim;i++,w=(LL)w*a%c) {
		if ((LL)w*sta%c == b) {printf("%d\n",i+cnt); return;} 
		else Hash::insert((LL)w*sta%c,i); 
	}
	
	for (int i=1,w=pow(a,lim,c),ori=w;i<=lim;i++,w=(LL)w*ori%c) {
		tmp = Hash::query(EX_GCD(w,c,b)); //if (i == 1) cout<<w<<endl;
		if (~tmp) {printf("%d\n",i*lim+tmp+cnt); return;}
	}
	printf("No Solution\n");
}

int main(){
	while (~scanf("%d%d%d",&a,&c,&b) && a) BSGS();
	return 0;
} 

这里有一份不带log的算法:http://paste.ubuntu.com/23021654/
不过我看不懂QAQ,就不管啦! *★,°*:.☆( ̄▽ ̄)/$:*.°★* 。

——— 2016.8.12更新 ———
不带log的版本,rank 3!

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long
using namespace std;
 
const double EPS = 1e-3;
const int MAXN = 100000;
 
int a,b,c;
 
namespace Hash{
    const int MOD = 99971;
    int head[MAXN],nxt[MAXN],val[MAXN],data[MAXN],T;
     
    inline void init(){memset(head,0,sizeof(head)); T=0;}
     
    inline void insert(int v, int d) {
        nxt[++T] = head[v%MOD];
        val[T] = v; data[T] = d; 
        head[v%MOD] = T;
    }
     
    inline int query(int v){
        for (int i=head[v%MOD];i;i=nxt[i]) 
            if (val[i] == v) return data[i];
        return -1;
    }
};
 
inline int pow(int w, int t, int p){
    int ret = 1;
    while (t) {
        if (t & 1) ret  = (LL)ret*w % p;
        w = (LL)w*w % p; t >>= 1;
    } 
    return ret;
}
 
int GCD(int a, int b) {return b?GCD(b,a%b):a;}
 
void EX_GCD(int a, int b, LL &x, LL &y) {
    if (!b) x = 1, y = 0;
    else EX_GCD(b,a%b,y,x), y -= a/b*x;
}
 
inline int EX_GCD(int a, int b, int pur){
    LL ret,tmp; EX_GCD(a,b,ret,tmp);
    return (ret*pur%b+b) % b; 
}
 
inline void BSGS(){
    int cnt = 0,tmp,sta=1,sld[32],A=a,B=b,C=c; a %= c; b %= c; 
    while ((tmp=GCD(a,c)) > 1)
        if (b % tmp) {printf("No Solution\n"); return;}  
        else sld[++cnt] = a / tmp, b /= tmp, c /= tmp;  
    for (int i=0;i<=cnt;i++) if (pow(A,i,C) == B%C) {printf("%d\n",i); return;} 
    for (int i=1;i<=cnt;i++) sta = (LL)sta*sld[i]%c;
     
    Hash::init(); 
    int lim = int(ceil(sqrt(c)) + EPS);
    for (int i=0,w=1;i<=lim;i++,w=(LL)w*a%c) {
        if ((LL)w*sta%c == b) {printf("%d\n",i+cnt); return;} 
        else Hash::insert((LL)w*sta%c,i); 
    }
    
	int w_ori = pow(a,lim,c), rev_ori = EX_GCD(w_ori,c,1); 
    for (int i=1,rev=rev_ori;i<=lim;i++,rev=(LL)rev*rev_ori%c) {
        tmp = Hash::query((LL)rev*b%c); 
        if (~tmp) {printf("%d\n",i*lim+tmp+cnt); return;}
    }
    printf("No Solution\n");
}
 
int main(){
    while (~scanf("%d%d%d",&a,&c,&b) && a) BSGS();
    return 0;
} 

—– UPD 2016.9.19 —–
之前的程序仍然有bug,会被3 9 3这种数据卡掉
非常感谢wyh神犇提供的数据 _(:зゝ∠)_
这是改正之后的程序:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const double EPS = 1e-3;
const int MAXN = 100000;
 
int a,b,c;
 
namespace Hash{
    const int MOD = 99971;
    int head[MAXN],nxt[MAXN],val[MAXN],data[MAXN],T;
     
    inline void init(){memset(head,0,sizeof(head)); T=0;}
     
    inline void insert(int v, int d) {
        nxt[++T] = head[v%MOD];
        val[T] = v; data[T] = d; 
        head[v%MOD] = T;
    }
     
    inline int query(int v){
        for (int i=head[v%MOD];i;i=nxt[i]) 
            if (val[i] == v) return data[i];
        return -1;
    }
};
 
inline int pow(int w, int t, int p){
    int ret = 1;
    while (t) {
        if (t & 1) ret  = (LL)ret*w % p;
        w = (LL)w*w % p; t >>= 1;
    } 
    return ret;
}
 
int GCD(int a, int b) {return b?GCD(b,a%b):a;}
 
void EX_GCD(int a, int b, LL &x, LL &y) {
    if (!b) x = 1, y = 0;
    else EX_GCD(b,a%b,y,x), y -= a/b*x;
}
 
inline int EX_GCD(int a, int b, int pur){
    LL ret,tmp; EX_GCD(a,b,ret,tmp);
    return (ret*pur%b+b) % b; 
}

inline void SPJ(int A, int B, int C, int cnt){
	for (int i=0;i<=cnt;i++) if (pow(A,i,C) == B%C) {printf("%d\n",i); return;}
	printf("No Solution\n"); 
}
 
inline void BSGS(){
    int cnt = 0,tmp,sta=1,sld[32],A=a,B=b,C=c; a %= c; b %= c; 
    while ((tmp=GCD(a,c)) > 1)
        if (b % tmp) {SPJ(A,B,C,cnt);return;}  
        else sld[++cnt] = a / tmp, b /= tmp, c /= tmp;  
    for (int i=0;i<=cnt;i++) if (pow(A,i,C) == B%C) {printf("%d\n",i); return;} 
    for (int i=1;i<=cnt;i++) sta = (LL)sta*sld[i]%c;
     
    Hash::init(); 
    int lim = int(ceil(sqrt(c)) + EPS);
    for (int i=0,w=1;i<=lim;i++,w=(LL)w*a%c) {
        if ((LL)w*sta%c == b) {printf("%d\n",i+cnt); return;} 
        else Hash::insert((LL)w*sta%c,i); 
    }
     
    for (int i=1,w=pow(a,lim,c),ori=w;i<=lim;i++,w=(LL)w*ori%c) {
        tmp = Hash::query(EX_GCD(w,c,b)); 
        if (~tmp) {printf("%d\n",i*lim+tmp+cnt); return;}
    }
    printf("No Solution\n");
}
 
int main(){
    while (~scanf("%d%d%d",&a,&c,&b) && a) BSGS();
    return 0;
}

2 thoughts to “【BZOJ 2995】同余方程”

  1. After I originally commented I clicked the -Notify me when new comments are added- checkbox and now every time a comment is added I get 4 emails with the same comment. Is there any manner you possibly can remove me from that service? Thanks!

Leave a Reply

Your email address will not be published. Required fields are marked *