测算满足y^x ≡z(mod p)的细微非负整数x,输入格式710官方网站

标题叙述

你被须要设计一个计算器实现以下三项职务:

1、给定y、z、p,计算y^z mod p 的值;

2、给定y、z、p,总结满意xy ≡z(mod p)的纤维非负整数x;

3、给定y、z、p,计算知足y^x ≡z(mod p)的一丝一毫非负整数x。

为了获得奖品,用尽全力吧!

P2485 [SDOI2011]计算器,p2485sdoi2011

输入输出格式

输入格式:

输入文件calc.in 包罗多组数据。

首先行包涵多少个正整数T、L,分别代表数据组数和理解项目(对于叁个测验点内的全部数

据,询问项目同样)。

以下T 行每行富含三个正整数y、z、p,描述一个询问。

输出格式:

输出文件calc.out 满含T 行.

对于各类询问,输出一行答案。

对此精通项目2 和3,假如空头支票满意条件的,则输出“Orz, I cannot find x!”。

主题材料汇报

您被供给设计一个计算器完结以下三项职务:

1、给定y、z、p,计算y^z mod p 的值;

2、给定y、z、p,总计知足xy ≡z(mod p)的小不点儿非负整数x;

3、给定y、z、p,计算满意y^x ≡z(mod p)的不大非负整数x。

为了得到奖品,尽心尽力吧!

输入输出样例

输入样例#1:

3 1
2 1 3
2 2 3
2 3 3

出口样例#1:

2
1
2

输入样例#2:

3 2
2 1 3
2 2 3
2 3 3

输出样例#2:

2
1
0

输入样例#3:

4 3
2 1 3
2 2 3
2 3 3
2 4 3

输出样例#3:

0
1
Orz, I cannot find x!
0

输入输出格式

输入格式:

输入文件calc.in 包涵多组数据。

率先行包蕴多少个正整数T、L,分别代表数据组数和询问项目(对于二个测量检验点内的全数数

据,询问项目一样)。

以下T 行每行李包裹罗多少个正整数y、z、p,描述贰个打探。

输出格式:

输出文件calc.out 包涵T 行.

对此每种询问,输出一行答案。

对于掌握项目2 和3,假诺不设有满意条件的,则输出“Orz, I cannot find x!”。

说明

710官方网站 1

 

思路:

率先问:裸急速幂

第二问:费马小定理 或然扩充欧几里得(解ax ≡ c (mod b))

第三问:裸BSGS

对于orz的判读

先是大家把上来先把y%p,把等式的侧面化成最简方式

对此第二问:先z%p,把等式右侧化成最简方式,在这种准绳下,要是y==0&&z!=0的情形下
y%b一定等于0而不容许等于z

对此第三问:假若y%p==0无解,因为费马小定理的准则是y与p互素

为了有助于清楚,小编把难题中的变量p改成了mod

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<map>
 6 using namespace std;
 7 typedef long long LL;
 8 LL n,how,y,z,p;
 9 map<LL,LL>mp;
10 LL fastpow(LL a,LL p,LL mod)
11 {
12     LL base=a;LL ans=1;
13     while(p!=0)
14     {
15         if(p%2==1)ans=(ans*base)%mod;
16         base=(base*base)%mod;
17         p=p/2;
18     }
19     return ans;
20 }
21 void bsgs(LL y,LL z,LL mod)
22 {
23     mp.clear();
24     if(y%mod==0)
25     {
26         printf("Orz, I cannot find x!\n");
27         return ;
28     }
29     LL m=ceil(sqrt(mod));
30     LL ans;
31     for(LL j=0;j<=m;j++)
32     {
33         if(j==0)
34         {
35             ans=z%mod;
36             mp[ans]=1;
37             continue;
38         }
39         ans=(ans*y)%mod;
40         mp[ans]=j;
41     }
42     ans=1;
43     LL t=fastpow(y,m,mod);
44     for(LL i=1;i<=m;i++)
45     {
46         ans=(ans*t)%mod;
47         if(mp[ans])
48         {
49             LL out=i*m-mp[ans];
50             printf("%d\n",(out%mod+mod)%mod);
51             return ;
52         }
53     }
54     printf("Orz, I cannot find x!\n");
55         
56 }
57 int main()
58 {
59     scanf("%d%d",&n,&how);
60     while(n--)
61     {
62         scanf("%d%d%d",&y,&z,&p);
63         y=y%p;
64         if(how==1)
65         printf("%d\n",fastpow(y,z,p));
66         else if(how==2)
67         {
68             z%=p;
69             if(y==0&&z!=0)
70             printf("Orz, I cannot find x!\n");
71             else
72             printf("%d\n",((z%p)*(fastpow(y,p-2,p))%p)%p);
73         }
74         else if(how==3)
75         bsgs(y,z,p);
76     }
77     return 0;
78 }

 

输入输出样例

输入样例#1:

3 1
2 1 3
2 2 3
2 3 3

输出样例#1:

2
1
2

输入样例#2:

3 2
2 1 3
2 2 3
2 3 3

出口样例#2:

2
1
0

输入样例#3:

4 3
2 1 3
2 2 3
2 3 3
2 4 3

输出样例#3:

0
1
Orz, I cannot find x!
0

说明

710官方网站 2

 

思路:

先是问:裸火速幂

第二问:费马小定理 或然 扩张欧几里得(解ax ≡ c (mod b))

第三问:裸BSGS

对于orz的判读

率先大家把上来先把y%p,把等式的右侧化成最简情势

对此第二问:先z%p,把等式左边化成最简格局,在这种原则下,假若y==0&&z!=0的气象下
y%b一定等于0而不容许等于z

对此第三问:倘使y%p==0无解,因为费马小定理的规格是y与p互素

为了便利清楚,笔者把难题中的变量p改成了mod

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<map>
 6 using namespace std;
 7 typedef long long LL;
 8 LL n,how,y,z,p;
 9 map<LL,LL>mp;
10 LL fastpow(LL a,LL p,LL mod)
11 {
12     LL base=a;LL ans=1;
13     while(p!=0)
14     {
15         if(p%2==1)ans=(ans*base)%mod;
16         base=(base*base)%mod;
17         p=p/2;
18     }
19     return ans;
20 }
21 void bsgs(LL y,LL z,LL mod)
22 {
23     mp.clear();
24     if(y%mod==0)
25     {
26         printf("Orz, I cannot find x!\n");
27         return ;
28     }
29     LL m=ceil(sqrt(mod));
30     LL ans;
31     for(LL j=0;j<=m;j++)
32     {
33         if(j==0)
34         {
35             ans=z%mod;
36             mp[ans]=1;
37             continue;
38         }
39         ans=(ans*y)%mod;
40         mp[ans]=j;
41     }
42     ans=1;
43     LL t=fastpow(y,m,mod);
44     for(LL i=1;i<=m;i++)
45     {
46         ans=(ans*t)%mod;
47         if(mp[ans])
48         {
49             LL out=i*m-mp[ans];
50             printf("%d\n",(out%mod+mod)%mod);
51             return ;
52         }
53     }
54     printf("Orz, I cannot find x!\n");
55         
56 }
57 int main()
58 {
59     scanf("%d%d",&n,&how);
60     while(n--)
61     {
62         scanf("%d%d%d",&y,&z,&p);
63         y=y%p;
64         if(how==1)
65         printf("%d\n",fastpow(y,z,p));
66         else if(how==2)
67         {
68             z%=p;
69             if(y==0&&z!=0)
70             printf("Orz, I cannot find x!\n");
71             else
72             printf("%d\n",((z%p)*(fastpow(y,p-2,p))%p)%p);
73         }
74         else if(how==3)
75         bsgs(y,z,p);
76     }
77     return 0;
78 }

 

http://www.bkjia.com/cjjc/1211715.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1211715.htmlTechArticleP2485 [SDOI2011]计算器,p2485sdoi2011 标题汇报你被供给设计三个计算器完结以下三项职分: 1、给定y、z、p,总结y^z mod p
的值; 2、给定y、z、…