首页 > 代码库 > 【Foreign】无聊的计算姬 [Lucas][BSGS]
【Foreign】无聊的计算姬 [Lucas][BSGS]
无聊的计算姬
Time Limit: 10 Sec Memory Limit: 256 MBDescription
Input
Output
Sample Input
6
2 2 3 4
3 2 7 9
2 1 2 9
3 1 6 7
1 5 3 7
1 9 2 8
Sample Output
Math Error
3
Math Error
6
6
1
HINT
Source
我们可以分步骗分。（Task1直接快速幂即可。）
对于前50分：
对于Task2，我们直接暴力枚举，出现一个重复的停止，判断是否存在即可，对于Task3，直接n^2递推组合数即可。
对于11~16的20分：
对于Task2，我们运用BSGS求解即可，对于Task3，直接上Lucas即可。
Code
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cmath> 8 #include<map> 9 using namespace std; 10 typedef long long s64; 11 12 const int ONE = 10000005; 13 14 map <int,int> f; 15 16 int T; 17 int type,y,z,MOD; 18 int Jc[ONE]; 19 int C[1005][1005]; 20 21 int get() 22 { 23 int res=1,Q=1; char c; 24 while( (c=getchar())<48 || c>57) 25 if(c==‘-‘)Q=-1; 26 if(Q) res=c-48; 27 while((c=getchar())>=48 && c<=57) 28 res=res*10+c-48; 29 return res*Q; 30 } 31 32 int Quickpow(int a,int b,int MOD) 33 { 34 int res=1; 35 while(b) 36 { 37 if(b&1) res=(s64)res*a%MOD; 38 a=(s64)a*a%MOD; 39 b>>=1; 40 } 41 return res; 42 } 43 44 namespace PC 45 { 46 int Make_C(int a,int b,int MOD) 47 { 48 C[0][0]=1; 49 for(int i=1;i<=a;i++) 50 { 51 C[i][0]=1; 52 for(int j=1;j<=b;j++) 53 C[i][j] = (C[i-1][j]+C[i-1][j-1]) % MOD; 54 } 55 return C[a][b]; 56 } 57 58 int C(int n,int m,int MOD) 59 { 60 int up = Jc[n]; 61 int down = (s64)Jc[m] * Jc[n-m] % MOD; 62 return (s64)up * Quickpow(down,MOD-2,MOD) % MOD; 63 } 64 65 int Lucas(int n,int m,int MOD) 66 { 67 Jc[0]=1; 68 for(int i=1;i<=MOD;i++) Jc[i] = (s64)Jc[i-1] * i % MOD; 69 int res = 1; 70 while(n && m) 71 { 72 res = (s64)res * C(n%MOD,m%MOD,MOD) % MOD; 73 n/=MOD; m/=MOD; 74 } 75 return res; 76 } 77 } 78 79 namespace PB 80 { 81 int Make_min(int a,int b,int MOD) 82 { 83 int res=1; 84 if(res==b) return 0; 85 f.clear(); 86 for(int i=1;i<=100000;i++) 87 { 88 res = (s64)res * a % MOD; 89 if(f[res]) return -1; 90 f[res] = 1; 91 if(res==b) return i; 92 } 93 return -1; 94 } 95 96 int BSGS(int A,int B,int MOD) 97 { 98 if(A % MOD == 0) return -1; 99 int m = sqrt(MOD) + 1;100 f.clear();101 int record = B % MOD;102 for(int i=1;i<=m;i++)103 {104 record = (s64) record * A % MOD;105 f[record] = i; 106 }107 108 int A_m = Quickpow(A,m,MOD);109 record = 1;110 for(int i=1;i<=m;i++)111 {112 record = (s64)record * A_m % MOD; 113 if(f[record])114 {115 int x = (i * m %MOD- f[record]+MOD) %MOD;116 return x;117 }118 }119 return -1;120 }121 }122 123 int main() 124 { 125 T=get();126 while(T--)127 {128 type=get();129 y=get(); z=get(); MOD=get();130 if(type==1) printf("%d\n",Quickpow(y,z,MOD));131 if(type==3) 132 {133 if(z<=1000 && y<=1000)134 printf("%d\n",PC::Make_C(z,y,MOD)); 135 else136 printf("%d\n",PC::Lucas(z,y,MOD));137 }138 if(type==2)139 {140 if(z<=1000 && y<=1000)141 {142 int res=PB::Make_min(y,z,MOD);143 if(res==-1) printf("Math Error\n");144 else printf("%d\n",res);145 }146 else147 {148 int res=PB::BSGS(y,z,MOD);149 if(res==-1) printf("Math Error\n");150 else printf("%d\n",res);151 }152 }153 } 154 }
【Foreign】无聊的计算姬 [Lucas][BSGS]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。