此文章可以使用目录功能哟↑(点击上方[+])
UVALive Problem 7457 Discrete Logarithm Problem
Accept: 0 Submit: 0
Time Limit: 3.000 seconds
Problem Description
Finite groups are used in almost all modern cryptosystems. Let p be a prime. The finite multiplicative group constructed by integers modulo p is denoted by 
You are going to write a program to solve the discrete logarithm problem in
For very large p, solving discrete logarithm problem in
Input
The first line of the input file contains a prime p, 1 < p < 2^13 . This prime will be used in the following test cases. Each test case contains two integers a and b in a line. The last test case is followed by a line containing ‘0’.
Output
For each test case, print out the solution x to the equation 
Sample Input
24 3
3 15
0
Sample Output
21
Problem Idea
解题思路:
【题意】
求满足
【类型】
暴力
【分析】
其实此题已经把题目简化了
因为它给了你x的范围为[1,p-1],然而p的值又很小,所以暴力枚举x的每种可能取值,判断等式是否成立即可
另外,我们提一提如果不给你x的范围应该怎么做
由费马小定理可得
这样我们就可以把x缩小至范围[0,p-2],然后暴力枚举就可以了
因此,此题暴力枚举也无需枚举到p-1,到p-2就可以了,若到p-2还没有满足的解x,那就是无解的情况了
此外要提及的一点是,输入除了单行'0'结束外,还要判断是否到文件尾(EOF),不然会超时(TLE)
【时间复杂度&&优化】
O(p)
题目链接→UVALive Problem 7457 Discrete Logarithm Problem
Source Code
/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 15;
const int M = 100005;
const int inf = 1000000007;
const int mod = 7;
int main()
{int p,a,b,i,s;scanf("%d",&p);while(~scanf("%d",&a)&&a)//'~'不能少,否则TLE{s=a%p;scanf("%d",&b);for(i=1;i<=p-2;i++,s=a%p*s%p)if(s==b)break;if(i>p-2)puts("0");elseprintf("%d\n",i);}return 0;
}