欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  互联网

洛谷OJ:P3846 [TJOI2007] 可爱的质数/【模板】BSGS(大步小步算法)

程序员文章站 2022-06-25 16:11:22
思路:BSGS模板题,并且该题由于数据范围不是太大,因此我们可以直接使用朴素的BSGS算法求解,算法讲解链接:BSGS简易讲解。#include#include#include#include#include#include#include#include#includ.....

洛谷OJ:P3846 [TJOI2007] 可爱的质数/【模板】BSGS(大步小步算法)

思路:BSGS模板题,并且该题由于b与p互质,因此我们可以直接使用朴素的BSGS算法求解,算法讲解链接:BSGS简易讲解

#include<set>
#include<map>
#include<queue>
#include<vector>
#include<string>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define maxn 100050
#define SQ 1005
#define ll long long
ll p,n,b;
ll q(ll x,ll y,ll m){
	ll res=1;
	x=x%m;
	while(y){
		if(y&1)
			res=res*x%m;
		x=x*x%m;
		y/=2;
	}
	return res;
}
ll BSGS(ll a,ll b,ll m){
	map<ll,ll> hs;
	ll cur=b*a%m,t=sqrt(m)+1;
	for(int B=1;B<=t;++B){
		hs[cur]=B;
		cur=cur*a%m;
	}
	ll at=q(a,t,m),now=at;
	for(int A=1;A<=t;A++){
		if(hs[now])
			return A*t-hs[now];
		now=now*at%m;
	}
	return -1;
}
int main(void){
	scanf("%lld%lld%lld",&p,&b,&n);
	ll ans=BSGS(b,n,p);
	if(ans==-1)
		printf("no solution\n");
	else
		printf("%lld\n",ans);
	return 0;
}

 

本文地址:https://blog.csdn.net/haut_ykc/article/details/109274720

相关标签: 数论