DLKKILL

DLKKILL's world

UVALive - 7457- Discrete Logarithm Problem (离散对数)

题目链接:UVALive – 7457

题目大意:

求同余方程《UVALive - 7457- Discrete Logarithm Problem (离散对数)》的解,其中《UVALive - 7457- Discrete Logarithm Problem (离散对数)》是素数 求A


题目分析:

这题数据量较小,可以直接暴力求得。

对于数据量大的,可以使用离散对数知识———->离散对数

注意sqrt运算较慢,多次求解时要优化提前求得s。

给出代码:

#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;
/*const int MAX_N=107;
string str;
int vis[MAX_N][MAX_N];
int dp[MAX_N][MAX_N];
int dfs(int l,int r)
{
    if(vis[l][r]) return dp[l][r];
    vis[l][r]=1;
    if(r-l<1)
    {
        dp[l][r]=0;
        return 0;
    }
    int a=-1,b=-1,c=-1;
    if(str[l]=='('&&str[r]==')') a=dfs(l+1,r-1)+1;
    for(int i<)
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        memset(vis,0,sizeof(vis));
        memset(dp,0,sizeof(vis));
        cin>>str;
    }
    return 0;
}*/
#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;
const int maxn=1e5+10;
int s;
long long pow_mod(long long a,long long i,long long n)
{
    if(i==0)
        return 1%n;
    int temp=pow_mod(a,i>>1,n);
    temp=temp*temp%n;
    if(i&1)
        temp=(long long)temp*a%n;
    return temp;
}
long long dis(int x,int n,int m)
{
    map<long long,int> rec;
    long long cur=1;
   /* int s=(int)(sqrt((double)p));
    for(;(long long )s*s<=p;)
        s++;  这里超时了两次)*/
    for(int i=0;i<s;i++)
    {
        rec[cur]=i;
        cur=cur*x%m;
    }
    long long mul=cur;
    cur=1;
    for(int i=0;i<s;i++)
    {
        long long more=(long long)n*pow_mod(cur,m-2,m)%m;
        if(rec.count(more))
        {
            return i*s+rec[more];
        }
        cur=cur*mul%m;
    }
    return -1;
}
int main()
{
    int p;
    scanf("%d",&p);
    s=(int)(sqrt((double)p));
    for(;(long long )s*s<=p;)
        s++;
    int a,b;
    while(scanf("%d",&a)!=EOF&&a)
    {
        scanf("%d",&b);
        long long int ans=dis(a,b,p);
        if(ans==-1)
            ans=0;
        printf("%lld\n",ans);
    }
    return 0;
}

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注