hdu5690 快速模幂

2019-04-13 17:29发布

站内文章 / 模拟电子
9908 0 1475
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5690 题目大意：F(x,m) 代表一个全是由数字x组成的m位数字。请计算，以下式子是否成立：

F(x,m) mod k ≡ c
思路：因为有m个x，还有取模操作，所以可以快速模幂把m位的x对k取模的结果求出来，然后在和c对k取模结果比较即可。因为取模是有个除法操作 所以可以用逆元，也可以直接乘到k上面去。。
#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; //#pragma comment(linker, "/STACK:102400000,102400000") #define maxn 200005 #define MOD 1000000007 #define mem(a , b) memset(a , b , sizeof(a)) #define LL long long #define ULL unsigned long long const long long INF=0x3fffffff; LL ans ; LL x , m , k , c; LL quick_pow(LL m , LL mod) { LL res = 1; LL tmp = 10; while(m) { if(m & 1) { res *= tmp; res %= mod; } tmp *= tmp; tmp %= mod; m >>= 1; } return res; } int main() { int t , ncase = 1; scanf("%d" , &t); while(t--) { scanf("%lld %lld %lld %lld" , &x , &m , &k , &c); k *= 9; LL ans = quick_pow(m , k); ans = ( (ans - 1 + k) % k); ans = (ans *x) % k; printf("Case #%d: " , ncase ++); if(ans == (c*9)%k) printf("Yes "); else printf("No "); } return 0; }

热门文章