이산 대수 - BSGS 알고리즘

58682 단어 수론BSGS
구호
참고: 큰 걸음 작은 걸음 으로 이산 대수 문 제 를 해결 합 니 다.
이산 대 수 는 주로 이런 문 제 를 해결 하 는 것 이다.
a. x. 1. b (m o d m) a ^ x \ equiv b \ \ pmod m ax. 1. 1. b (modm) 는 대개 (m o d m) \ pmod m (modm) 의미 에서 의 대수 입 니 다.
여 기 는 (m, a) (m, a) (m, a) 가 1 인 경우 만 고려 합 니 다.일반적으로 제 시 된 m 는 하나의 양수 이다.
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ rceil + B x \ \ \ \ \ \ \ \ \ \ \ lceil \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ il 0 ≤ A < ⌈ p ⌉.방정식
(m o d p) a ^ {A \ \ \ \ lceil \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ sqrt {p} \ \ \ rceil + B} \ \ \ \ \ equiv b \ \ \ \ \ pmod p \ \ \ p p \ \ p p p \ \ p p p \ \ p p p \ \ \ \ \ \ \ \ \ \ \ \ \ rce일 A \ \ \ \ \ rce일 A * p \ \ \ \ \ \ rce일 A * p \ \ 8968 p 의 역 원 을 곱 하면 방정식 이 a 로 바 뀌 고, 방정식 이 A 로 바 뀌 고, A B 가 A 로 바 뀌 고, A B 가 A \ \ \ \ \ \ \ \ \ \ lceil \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (m o d p) a ^ {B} \ equiv b \ \ cdot a ^ {- A \ \ lceil \ \ sqrt {p} \ \ rceil} \ \ pmod p aB ▼ b ⋅ a − A ⌈ p ⌉ (modp)A A, B B B 는 모두 O (p) O (\ sqrt {p}) O (p) 등급 의 수 이기 때문에 왼쪽 의 모든 값 을 미리 처리 한 다음 작은 순서 로 A A A 를 매 거 하여 왼쪽 에 값 이 대응 하 는 지 찾 을 수 있 습 니 다.손 으로 h a s h hash 또는 C + + 11 의 u n o r d e d unordered unorderedm a p map 는 O (1) O (1) O (1) 시간 조회 가 가능 합 니 다.이러한 복잡 도 는 O (p + p) O (\ sqrt {p} + \ sqrt {p}) O (p + p) 의 것 이다.
n n 개 b b b 에 대해 이 방정식 을 풀 필요 가 있다 면 x x x 를 A * 8727 ° K + B A * K + B A * 8727 ° K + B 로 표시 하 는 것 을 고려 하면 A ≤ * 8970 ° p k * 8971 ° A \ \ leq \ lfloor \ frac {p} {k} \ rfloor A ≤ * 8970 ° kp * 8971 °, 왼쪽 을 미리 처리 한 후 오른쪽 에서 n n 회 만 반복 하면 됩 니 다.시간 복잡 도 는 O (K + * 8970 ° p k * 8971 ° n) O (K + \ lfloor \ \ frac {p} {k} \ rfloor * n) O (K + * 8970 ° kp * 8727 ° n) 입 니 다.
code:
x y = n m o d & ThinSpace;   m x ^ y = n \ mod m xy = nmodm 구 해 y y y.
LL discrete_log(int x,int _n,int m){
	unordered_map<LL,int>rec;
	int s=(int)(sqrt((double)m));
	for(; (LL)s*s<=m;)++s;
	LL cur=1;
	for(int i=0;i<s;++i){
		rec[cur]=i;
//		cur=cur*x%m;
		MUL(cur,x,m);
	}
	LL mul=cur;
	cur=1;
	for(int i=0;i<s;++i){
		LL more=(LL)_n;
		MUL(more,qpow(cur,m-2,m),m);
		if(rec.count(more)){
			return i*s +rec[more];
		}
//		cur= cur*mul%m;
		MUL(cur,mul,m);
	}
	return -1;
}

월 드 컵 E
#include

using namespace std;

#define lson rt<<1
#define rson rt<<1|1

typedef long long ll;
const int mod = 1e9+7;
const int _mod = mod - 1;
const int _P = 5;
const int maxn = 1e5+10;

ll a[maxn],Log[maxn];

struct node{
    int l,r;
    ll sum,add,mul;
}tr[maxn<<2];

void Add(ll& x,ll y,int P){
    x+=y;
    if(x>=P) x -= P;
}

void Mul(ll& x,ll y,int P){
    x *= y;
    if(x>=P) x %= P;
}

ll qpow(ll a,ll b,ll P){
    ll ret = 1;
    while(b){
        if(b&1) Mul(ret,a,P);
        Mul(a,a,P);
        b>>=1;
    }
    return ret;
}

void up(int rt){
    tr[rt].sum = tr[lson].sum + tr[rson].sum;
    if(tr[rt].sum >= _mod) tr[rt].sum -= _mod;
}

void down(int rt){
    int m = (tr[rt].l + tr[rt].r)>>1;
    // cout<
    // cout<
    if(tr[rt].mul > 1){
        int c = tr[rt].mul;
        Mul(tr[lson].mul,c,_mod);
        Mul(tr[rson].mul,c,_mod);
        Mul(tr[lson].sum,c,_mod);
        Mul(tr[rson].sum,c,_mod);
        Mul(tr[lson].add,c,_mod);
        Mul(tr[rson].add,c,_mod);
        tr[rt].mul = 1;
    }
    if(tr[rt].add > 0){
        int c = tr[rt].add;
        Add(tr[lson].add,c,_mod);
        Add(tr[rson].add,c,_mod);
        Add(tr[lson].sum,(ll)(m-tr[rt].l + 1) * c % _mod,_mod);
        Add(tr[rson].sum,(ll)(tr[rt].r - m) * c % _mod,_mod);
        tr[rt].add = 0;
    } 
}

void build(int rt,int L,int R){
    // cout<
    tr[rt].l = L;
    tr[rt].r = R; 
    tr[rt].add = 0;
    tr[rt].mul = 1;
    if(L == R){
        tr[rt].sum = a[L];
        return ;
    }
    int m = (L+R)>>1;
    build(lson,L,m);
    build(rson,m+1,R);
    up(rt);
}

void update(int rt,int L,int R,int v,int k){
    if(L <= tr[rt].l && tr[rt].r <= R){
        if(k == 1){            
            Add(tr[rt].sum,(ll)(tr[rt].r - tr[rt].l + 1) * v % _mod,_mod);
            Add(tr[rt].add,v,_mod);
        }
        else{
            Mul(tr[rt].sum,v,_mod);
            Mul(tr[rt].mul,v,_mod);
            Mul(tr[rt].add,v,_mod);
        }
        return ;
    }
    down(rt);
    int m = (tr[rt].l + tr[rt].r) >> 1;
    if(L <= m) update(lson,L,R,v,k);
    if(m < R) update(rson,L,R,v,k);
    up(rt);
}

ll query(int rt,int L,int R){
    // cout<
    if(L <= tr[rt].l && tr[rt].r <= R) return tr[rt].sum;
    down(rt);
    int m = (tr[rt].l + tr[rt].r) >> 1;
    ll ret = 0;
    if(L <= m) Add(ret,query(lson,L,R),_mod);
    if(m < R) Add(ret,query(rson,L,R),_mod);
    return ret;
}

const int K = 300000;
unordered_map<ll,int> rec;
ll Base;

ll get_log(int x,int _n,int m){
	ll mul = Base;
	ll cur=1;
	for(int i=0;i<K;++i){
		ll more=(ll)_n;
		Mul(more,qpow(cur,m-2,m),m);
		if(rec.count(more)){
			return i*K + rec[more];
		}
		Mul(cur,mul,m);
	}
	return -1;
}

bool check[2005];

void init(){
    memset(check,false,sizeof(check));
	ll cur = 1;
	for(int i = 0;i<K;i++){
		rec[cur] = i;
		Mul(cur,_P,mod);
	}
	Base = cur;
    Log[1] = get_log(_P,1,mod);
    for(int i = 2;i< 1005;i++){
        if(!check[i]){
            Log[i] = get_log(_P,i,mod) % _mod;
        }
        for(int j = i * 2; j < 1005;j += i){
            check[j] = true;
            Log[j] = Log[j/i] + Log[i];
            if(Log[j] >= _mod) Log[j] -= _mod;
        }
    }
}

int main(){
    init();
    int cas; scanf("%d",&cas);
    while(cas--){
        int n,q;
        scanf("%d%d",&n,&q);
        for(int i = 1;i<=n;i++){
            scanf("%lld",&a[i]);
            a[i] = Log[a[i]];
        }
        build(1,1,n);
        // cout<
        while(q--){
            int op,l,r,v,k;
            scanf("%d",&op);
            if(op == 1){
                scanf("%d%d%d",&l,&r,&v);
                update(1,l,r,Log[v],1);
                // update(1,l,r,v,1);
            }
            else if(op == 2){
                scanf("%d%d%d",&l,&r,&k);
                update(1,l,r,k,2);
            }
            else {
                scanf("%d%d",&l,&r);
                ll ans = query(1,l,r);
                ans = qpow(_P,ans,mod);
                printf("%lld
"
,ans); } } } return 0; }

좋은 웹페이지 즐겨찾기