• 周四. 12 月 12th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

【zoj3254】Secret Code

admin

11 月 28, 2021

题意:

给出a、p、d、m 求a^x=d(mod p) 0<=x<=m 的解的个数

题解:

今天一整天的时间大部分都在调这题Orz BSGS什么的还是太不熟了

我们可以用BSGS拓展版求出最小解x 以及循环节开始的位置start start就是p被除(a,p)的次数

如果不存在解x 或x>m则输出0

如果x<start 那么输出1 因为如果解在循环节之前 在循环节中就不可能有x的解

如果start<=x<=m 答案就是x循环出现的次数=(m-x)/lon (lon是循环节长度)

这有些地方要注意的

因为题目的m<=2^63-1 而0<=x<=m 所以可能导致答案爆long long 要开unsigned long long

还有该mod的地方要mod啊 因为一个mod 我段异常了一个早上

然后因为对BSGS不熟 WA了一下午TAT 按AK大神的打法重打一遍才过

代码:

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 typedef long long ll;
  5 typedef unsigned long long ull;
  6 const ll mo=200003,N=20000;
  7 ll a,p,d,m,sum=1,sq,hash[mo],hat[mo],pri[N],save[N],bo[N+1],tot,add;
  8 ll gcd(ll a,ll b){ return b ? gcd(b,a%b) : a; }
  9 ll extgcd(ll &x,ll &y,ll a,ll b){
 10     if (!b){
 11         x=1,y=0;
 12         return a;
 13     }else{
 14         ll res=extgcd(x,y,b,a%b),t=x;
 15         x=y,y=t-a/b*y;
 16         return res;
 17     }
 18 }
 19 void push(ll x,ll y){
 20     ll t=x%mo;
 21     while (hash[t]>=0){
 22         if (hash[t]==x) return;
 23         t=(t+1)%mo;
 24     }
 25     hash[t]=x,hat[t]=y;
 26 }
 27 void makehash(){
 28     for (ll i=0,x=1%p;i<sq;i++,x=x*a%p) push(x,i);
 29 }
 30 ll ha(ll x){
 31     ll t=x%mo;
 32     while (hash[t]>=0){
 33         if (hash[t]==x) return hat[t];
 34         t=(t+1)%mo;
 35     }
 36     return -1;
 37 }
 38 ll mi(ll a,ll b){
 39     ll res=1;
 40     for (;b;b>>=1){
 41         if (b&1) res=res*a%p;
 42         a=a*a%p;
 43     }
 44     return res;
 45 }
 46 ll makex(){
 47     ll x,y,a1,b1=p,res;
 48     for (ll i=0;i<=sq;i++){
 49         a1=mi(a,sq*i)*sum%p;
 50         ll gc=extgcd(x,y,a1,b1),xx=b1/gc;
 51         if (d%gc) continue;
 52         x=(d/gc*x%xx+xx)%xx;
 53         res=ha(x);
 54         if (res>=0 && res<=p)
 55         return i*sq+res+add;
 56     }
 57     return -1;
 58 }
 59 void makepri(){
 60     for (ll i=2;i<=N;i++){
 61         if (!bo[i]) pri[++pri[0]]=i;
 62         for (ll j=1;j<=pri[0] && i*pri[j]<=N;j++){
 63             bo[i*pri[j]]=1;
 64             if (!(i%pri[j])) break;
 65         }
 66     }
 67 }
 68 bool check(ll t){ return mi(a,t)==1; }
 69 void makesave(ll x){
 70     save[0]=0;
 71     for (ll i=1;i<=pri[0] && x>1;++i)
 72     if (!(x%pri[i])){
 73         save[++save[0]]=pri[i];
 74         while (!(x%pri[i])) x/=pri[i];
 75     }
 76     if (x>1) save[++save[0]]=x;
 77 }
 78 ll phi(ll t){
 79     makesave(t);
 80     ll res=t;
 81     for (ll i=1;i<=save[0];i++)
 82     res=res/save[i]*(save[i]-1);
 83     return res;
 84 }
 85 ll makelon(){
 86     ll t=phi(p);
 87     makesave(t);
 88     for (ll i=1;i<=save[0];i++)
 89     while (check(t/save[i]) && !(t%save[i])) t/=save[i];
 90     return t;
 91 }
 92 int bsgs(){
 93     int addx=1,sd=d,sp=p;
 94     for (int gc=gcd(a,p);gc>1;gc=gcd(a,p)){
 95         if (addx==sd) return add++;
 96         if (d%gc) return -1;
 97         addx=addx*a%sp;
 98         d/=gc,p/=gc;
 99         sum=a/gc*sum%p;
100         ++add;
101     }
102     sq=(ll)sqrt(p);
103     a%=p;
104     makehash();
105     return makex();
106 }
107 void work(){
108     ull res=0;
109     add=0,sum=1;
110     memset(hash,-1,sizeof(hash));
111     ll x=bsgs();
112     if (x==-1 || x>m){
113         puts("0");
114         return ;
115     }else if (x<add){
116         puts("1");
117         return;
118     }
119     ll lon=makelon();
120     res=(m-x)/lon+1;
121     printf("%I64u
",res);
122 } 
123 int main(){
124     makepri();
125     while (scanf("%I64d%I64d%I64d%I64d",&a,&p,&d,&m)!=EOF){
126         ++tot;
127         //printf("%d:",tot);
128         a%=p;
129         work();
130     }
131 }

View Code

发表回复