Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
题目描述：
二进制数n mod m的结果是多少？
对于二进制数的取模运算，我们的第一反应一定是模拟其减法运算，然后逐位相减。但是这道题的数据达到了$2e5$，鉴于减法模拟的巨大常数，一定是会$T$的.所以说我们换一个角度考虑这个问题——数论。看到取模我就想起来那个当年那个坑了我两个小时的取模分配率，然后我又注意到题目里那个比较小的数字，m的长度最大为$20$，我可以先把m处理为10进制作为整个题的$moder$，然后用这个$moder$，一边用快速幂将n转为$10$进制一边取模，时间复杂度$O(m+n)$。
#include<bits/stdc++.h> using namespace std; long long suma, sumb, x, y; int lena, lenb; char a[200100], b[100]; int f[200100]; int main() { scanf("%s", a); scanf("%s", b); lena = strlen(a); lenb = strlen(b); x = 1; for (int i = lenb - 1; i >= 0; i --){ if (b[i] == '1') sumb += x; x = x * 2; } y = 1; for (int i = lena - 1; i >= 0; i --){ if (a[i] == '1') suma = (suma + y); suma %= sumb; y = (y * 2); y %= sumb; } while (true){ f[0] ++; f[f[0]] = suma % 2; suma /= 2; if (suma == 0) break; } if (!f[0]){ printf("0\n"); return 0; } for (int i = f[0]; i >= 1; i --) printf("%d", f[i]); return 0; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/167889.html原文链接：https://javaforall.net
