HDU 5690 查找循环节 数学公式快速幂+乘法逆元（除法取模）

2019-04-14 17:41发布

站内文章 / 模拟电子
14087 0 1115
方法一 ：因为m为10^10 次方，很大，所以猜测应该会出现循环节， 于是找到循环节映射出来即可 方法二： m个x组成的数可以表示为x*(1+10+10^2+...+10^m-1)=x*(10^m-1)/9; 即x*(10^m-1)/9%k==c     x*(10^m-1)%(9*k)==9*c 用快速幂去做去做。
#include #include #include #define LL long long #define INF 0x3f3f3f3f #define bug puts("**********"); using namespace std; int vis2[200000]; int vis[1100000]; int main() { LL x,m,k,c; int t; scanf("%d",&t); for(int cas=1; cas<=t; cas++) { scanf("%lld%lld%lld%lld",&x,&m,&k,&c); LL sum=0; memset(vis2,-1,sizeof(vis2)); int start=-1,bit=0; printf("Case #%d: ",cas); for(int i=0; i=start) ///判断是否到达了循环的部分 { if(vis[(m-start-1)%bit+start]==c) ///哈希得到值 puts("Yes"); else puts("No"); } else { if(vis[m]==c) puts("Yes"); else puts("No"); } } } return 0; }

热门文章