BZOJ 2242 [SDOI2011] 计算器

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2242

题意：给出 a,b,p, 分别求：

求\(a^b \ mod \ p\)

求最小的非负整数 x 满足 \(a\cdot x\equiv b \ (\ mod\ p \ )\)。

求最小的非负整数 x 满足 \(a^x\equiv b \ (\ mod\ p \ )\)。

这题数据强一点吧... ~~爆 long long 会死的很惨~~ ...

有一个没啥用的小优化，发现 p 不一定是质数，每次枚举上界处理到 phi(p) 即可，但是由于要暴力求 phi(p) 反而会变慢一点...

#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 100000
#define ll long long
using namespace std;
char xB[1<<15],*xS=xB,*xT=xB;
#define getchar() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T,k;
int a,b,p;
int quickmod(int a,int b)
{
    int ret=1;
    while(b)
    {
        if(b&1)ret=(ll)ret*a%p;
        b>>=1,a=(ll)a*a%p;
    }
    return ret;
}
namespace subtask1
{
    void main()
    {
        while(T--)
        {
            a=read(),b=read(),p=read();
            printf("%d\n",quickmod(a,b));
        }
    }
}
namespace subtask2
{
    inline int gcd(int a,int b)
    {return b==0?a:gcd(b,a%b);}
    int x,y;
    void exgcd(int a,int b,int &x,int &y)
    {
        if(b==0)
        {
            x=1,y=0;
            return ;
        }
        exgcd(b,a%b,x,y);
        int tmp=x;
        x=y,y=tmp-a/b*y;
        return ;
    }
    void main()
    {
        while(T--)
        {
            a=read(),b=read(),p=read();
            int k=gcd(a,p);
            if(b%k)
            {
                puts("Orz, I cannot find x!");
                continue ;
            }
            a/=k,p/=k;
            exgcd(a,p,x,y);
            x=(ll)x*b%p;
            printf("%d\n",(x+p)%p);
        }
    }
}
namespace subtask3
{
    map<int,int> f;
    int phi(int x)
    {
        int ret=x;
        for(int i=2;i*i<=x;i++)
        if(x%i==0)
        {
            ret-=ret/i;
            while(x%i==0)x/=i;
        }
        if(x>1)ret-=ret/x;
        return ret;
    }
    void main()
    {
        while(T--)
        {
            a=read(),b=read(),p=read();
            a%=p,b%=p;
            if(!a&&!b){puts("1");continue ;}
            if(!a){puts("Orz, I cannot find x!");continue ;}
            bool flag=0;
            f.clear();
            int m=ceil(sqrt(phi(p)));
            int bas=quickmod(a,m),pos=b;
            for(int j=0;j<=m;j++)
            {
                if(j!=0)pos=(ll)pos*a%p;
                f[pos]=j;
            }
            pos=bas;
            for(int i=1;i<=m;i++,pos=(ll)pos*bas%p)
            if(f.count(pos))
            {
                flag=1;
                printf("%d\n",i*m-f[pos]);
                break ;
            }
            if(!flag) puts("Orz, I cannot find x!");
        }
    }
}
int main()
{
    T=read(),k=read();
    if(k==1)subtask1::main();
    if(k==2)subtask2::main();
    if(k==3)subtask3::main();
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

#include <map>

#include <cmath>

#include <queue>

#include <cstdio>

#include <iomanip>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 100000

#define ll long long

using namespace std;

char xB[1<<15],*xS=xB,*xT=xB;

#define getchar() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int T,k;

int a,b,p;

int quickmod(int a,int b)

{

int ret=1;

while(b)

{

if(b&1)ret=(ll)ret*a%p;

b>>=1,a=(ll)a*a%p;

}

return ret;

}

namespace subtask1

{

void main()

{

while(T--)

{

a=read(),b=read(),p=read();

printf("%d\n",quickmod(a,b));

}

namespace subtask2

{

inline int gcd(int a,int b)

{return b==0?a:gcd(b,a%b);}

int x,y;

void exgcd(int a,int b,int &x,int &y)

{

if(b==0)

{

x=1,y=0;

return ;

}

exgcd(b,a%b,x,y);

int tmp=x;

x=y,y=tmp-a/b*y;

return ;

}

void main()

{

while(T--)

{

a=read(),b=read(),p=read();

int k=gcd(a,p);

if(b%k)

{

puts("Orz, I cannot find x!");

continue ;

}

a/=k,p/=k;

exgcd(a,p,x,y);

x=(ll)x*b%p;

printf("%d\n",(x+p)%p);

}

namespace subtask3

{

map<int,int> f;

int phi(int x)

{

int ret=x;

for(int i=2;i*i<=x;i++)

if(x%i==0)

{

ret-=ret/i;

while(x%i==0)x/=i;

}

if(x>1)ret-=ret/x;

return ret;

}

void main()

{

while(T--)

{

a=read(),b=read(),p=read();

a%=p,b%=p;

if(!a&&!b){puts("1");continue ;}

if(!a){puts("Orz, I cannot find x!");continue ;}

bool flag=0;

f.clear();

int m=ceil(sqrt(phi(p)));

int bas=quickmod(a,m),pos=b;

for(int j=0;j<=m;j++)

{

if(j!=0)pos=(ll)pos*a%p;

f[pos]=j;

}

pos=bas;

for(int i=1;i<=m;i++,pos=(ll)pos*bas%p)

if(f.count(pos))

{

flag=1;

printf("%d\n",i*m-f[pos]);

break ;

}

if(!flag) puts("Orz, I cannot find x!");

}

int main()

{

T=read(),k=read();

if(k==1)subtask1::main();

if(k==2)subtask2::main();

if(k==3)subtask3::main();

}

zgz233

zgz233

BZOJ 2242 [SDOI2011] 计算器

l1ll5

Comments | NOTHING