poj 2417 小步大步算法+费马小定理求逆元

2017年04月30日 21点热度 0人点赞 0条评论
/*小步大步算法+费马小定理求逆元
如果p为素数,a为整数,则a^(p-1)=1(mod p) -> a^(p-2)=(a^(-1))(mod p),又想了下,这个条件成立要a A^j===B*A^(-i*m)(MOD C)
我们先预处理A^0,A^1,A^2……A^(m-1),存入HASH表。,这一步就是baby-step,每次移动1
然后求出A^-m,枚举i,如果存在A^(-i*m)存在于HASH表中,说明存在解x=i*m+j    ,这一步为giant_step,每次移动m
至于B^(-m)的求法,可以先求出B的逆元,也就是B^-1。
注意以上解法是最基本的,只能对于C为素数 
*/
//数据比较大,凡是有相乘的地方都要注意溢出 
//Accepted	4608K	4032MS	G++	1365B 莫名通过 
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
ll C,A,B;
ll fast_pow(ll a,ll b){
	//求解(a^b)%C的值
	ll ans=1;
	while(b){
		if(b&1) ans=(ans*a)%C;
		b>>=1;
		a=(a*a)%C;
	}
	return ans;
}
int main(){
	while(~scanf("%lld%lld%lld",&C,&A,&B)){
		int m=(int)ceil(sqrt(C));
		map hash;
		set vis;
		map::iterator it,end=hash.end();
		for(int i=0;i
//莫名加速 Accepted	5628K	2454MS	G++ 
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
ll C,A,B;
ll fast_pow(ll a,ll b){
	//求解(a^b)%C的值
	ll ans=1;
	while(b){
		if(b&1) ans=(ans*a)%C;
		b>>=1;
		a=(a*a)%C;
	}
	return ans;
}
int main(){
	while(~scanf("%lld%lld%lld",&C,&A,&B)){
		int m=(int)ceil(sqrt(C));
		map hash;
		map vis;
		map::iterator it,end=hash.end();
		for(int i=0;i

//莫名超时 
#include
#include
#include
#include
#define ll long long
using namespace std;
ll C,A,B;
ll fast_pow(ll a,ll b){
	//求解(a^b)%C的值
	ll ans=1;
	while(b){
		if(b&1) ans=(ans*a)%C;
		b>>=1;
		a=(a*a)%C;
	}
	return ans;
}
int main(){
	while(~scanf("%lld%lld%lld",&C,&A,&B)){
		int m=(int)ceil(sqrt(C));
		map hash;
		map::iterator it,end=hash.end();
		for(int i=0;isecond;
				break;
			}
			tt=(tt*t)%C;
		}
		if(ans==-1)
		puts("no solution");
		else
		printf("%lldn",ans);
	}
	return 0;
}

//莫名超时 
#include
#include
#include
#include
#define ll long long
using namespace std;
ll C,A,B;
ll fast_pow(ll a,ll b){
	//求解(a^b)%C的值
	ll ans=1;
	while(b){
		if(b&1) ans=(ans*a)%C;
		b>>=1;
		a=(a*a)%C;
	}
	return ans;
}
int main(){
	while(~scanf("%lld%lld%lld",&C,&A,&B)){
		int m=(int)ceil(sqrt(C));
		map hash;
		map::iterator it,end=hash.end();
		for(int i=0;i
Discrete Logging
Time Limit: 5000MS   Memory Limit: 65536K
Total Submissions: 5835   Accepted: 2604

Description

Given a prime P, 2 <= P < 231, an integer B, 2 <= B < P, and an integer N, 1 <= N < P, compute the discrete logarithm of N, base B, modulo P. That is, find an integer L such that 

    BL == N (mod P)

Input

Read several lines of input, each containing P,B,N separated by a space.

Output

For each line print the logarithm on a separate line. If there are several, print the smallest; if there is none, print "no solution".

Sample Input

5 2 1
5 2 2
5 2 3
5 2 4
5 3 1
5 3 2
5 3 3
5 3 4
5 4 1
5 4 2
5 4 3
5 4 4
12345701 2 1111111
1111111121 65537 1111111111

Sample Output

0
1
3
2
0
3
1
2
0
no solution
no solution
1
9584351
462803587

Hint

The solution to this problem requires a well known result in number theory that is probably expected of you for Putnam but not ACM competitions. It is Fermat's theorem that states 

   B(P-1) == 1 (mod P)

for any prime P and some other (fairly rare) numbers known as base-B pseudoprimes. A rarer subset of the base-B pseudoprimes, known as Carmichael numbers, are pseudoprimes for every base between 2 and P-1. A corollary to Fermat's theorem is that for any m 

   B(-m) == B(P-1-m) (mod P) .

用排序+二分查找,效率会提高10倍,因为本来数组就基本有序,所以排序的效率就高了,所以说还是不能刚看时间复杂度,还是要具体问题具体分析。

未经允许不得转载!poj 2417 小步大步算法+费马小定理求逆元

update

纸上得来终觉浅, 绝知此事须躬行。