「BZOJ2242」[SDOI2011] 计算器
Description
你被要求设计一个计算器完成以下三项任务：
1、给定y,z,p,计算Y^Z Mod P 的值；
2、给定y,z,p，计算满足xy≡ Z ( mod P )的最小非负整数；
3、给定y,z,p，计算满足Y^x ≡ Z ( mod P)的最小非负整数。
Input
输入包含多组数据。
第一行包含两个正整数T,K分别表示数据组数和询问类型（对于一个测试点内的所有数据，询问类型相同）。
以下行每行包含三个正整数y,z,p，描述一个询问。
Output
对于每个询问，输出一行答案。对于询问类型2和3，如果不存在满足条件的，则输出“Orz, I cannot find x!”，注意逗号与“I”之间有一个空格。
Sample Input
「样例输入1」
3 1
2 1 3
2 2 3
2 3 3
「样例输入2」
3 2
2 1 3
2 2 3
2 3 3
「数据规模和约定」
对于100%的数据，1<=y,z,p<=10^9，为质数，1<=T<=10。
3 1
2 1 3
2 2 3
2 3 3
「样例输入2」
3 2
2 1 3
2 2 3
2 3 3
「数据规模和约定」
对于100%的数据，1<=y,z,p<=10^9，为质数，1<=T<=10。
Sample Output
「样例输出1」
2
1
2
「样例输出2」
2
1
0
2
1
2
「样例输出2」
2
1
0
题解
sdoi计算器也顺便解决一下
第一问快速幂
第二问exgcd
第三问BSGS，好麻烦我就先略
为啥叫baby step giant step，我其实不是很懂
卓神说这是meet in the middle的一种运用
求\(y^x = z(mod~p)\)设\(x=km+i\)\[y^{km}*y^i\equiv z\]\(y^i\equiv z*ine(y^{km})\)(逆元)
用费马小定理显然可得\(ine(y^m)\equiv y^{p-1-m}\)设其为T
\[ine(y^{km})\equiv ine(y^{(k-1)m})*T\]
把\[y^i(0<=i<=m)\]放入hash或者map
然后枚举k，查询\[z*ine(y^{km})\]
显然m取\(\sqrt p\)复杂度比较优秀。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include<cstdio> #include<cmath> #include<ctime> #include<cstring> #include<iostream> #include<map> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int T,K; int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } 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 t=x;x=y;y=t-a/b*y; } int solve1(ll y,int z,int p) { y%=p; ll ans=1; for(int i=z;i;i>>=1,y=y*y%p) if(i&1)ans=ans*y%p; return ans; } void solve2(int y,int z,int p) { p=-p; int t=gcd(y,p); if(z%t){puts("Orz, I cannot find x!");return;} y/=t;z/=t;p/=t; int a,b;exgcd(y,p,a,b); a=(ll)a*z%p; while(a<0)a+=p; printf("%d\n",a); } map<int,int> mp; void solve3(int y,int z,int p) { y%=p; if(!y&&!z){puts("1");return;} if(!y){puts("Orz, I cannot find x!");return;} mp.clear(); ll m=ceil(sqrt(p)),t=1; mp[1]=m+1; for(ll i=1;i<m;i++) { t=t*y%p; if(!mp[t])mp[t]=i; } ll tmp=solve1(y,p-m-1,p),ine=1; for(ll k=0;k<m;k++) { int i=mp[z*ine%p]; if(i) { if(i==m+1)i=0; printf("%lld\n",k*m+i); return; } ine=ine*tmp%p; } puts("Orz, I cannot find x!"); } int main() { T=read();K=read(); while(T--) { int y=read(),z=read(),p=read(); if(K==1)printf("%d\n",solve1(y,z,p)); else if(K==2)solve2(y,z,p); else solve3(y,z,p); } return 0; } |
计数器 9793406
OI 课件=>
OI 课件=>
[…] 给个神犇题解链接 http://hzwer.com/5878.html […]
这份代码我卡掉了
1 3
1 1 2
为什么p要取成负数
不应该是m取sqrt（p）吗。。。
这个不要紧
要上取整没错呀