1046: 取模方程解的个数

时间限制: 1 Sec  内存限制: 128 MB
提交: 346  解决: 9
[提交][状态][讨论版][命题人:cyh]

题目描述

给定x和m,问在区间[a,b]上存在多少个i，使得x^i % 1000 = m。

输入

输入由多组数据构成。
每组数据一行，由四个空格分开的整数x、m、a和b组成。
0 <= x, m <= 1000000000
1 <= a <= b <= 1000000000

输出

每组输入数据产生一行输出，即使得上述等式成立的i的个数。

样例输入

13 13 1 100 13 12 1 100 13 13 1 1000000000

样例输出

1 0 10000000 找循环节，即第一次出现和第二次出现之间的间隔。有可能m只出现一次，而且由于【a，b】非常大，可以控制一下循环次数，避免超时，比如说200以内都没有出现循环节，那么之后也不会再出现循环节。 #include using namespace std; typedef long long LL; LL quickpow(LL x,LL i,LL m) { LL ans=1; while(i) { if(i&1) ans=(ans*x)%m; i=(i>>1); x=(x*x)%m; } return ans; } int main() { LL x,m,a,b; while(scanf("%lld%lld%lld%lld",&x,&m,&a,&b)==4) { if(m>=1000) { printf("0 "); continue; } LL L,R,cnt=0,ans=0; for(LL i=a;i<=b;) { if(i-a>=200&&cnt<2) break; if(cnt==2) { ans+=(b-R)/(R-L); break; } if(quickpow(x,i,1000)==m&&cnt==0) cnt++,L=i; else if(quickpow(x,i,1000)==m&&cnt==1) cnt++,R=i; i++; } if(cnt<=1) printf("%lld ",cnt); else printf("%lld ",ans+2); } }