二进制除法_111011001÷1011二进制除法

全栈程序员站长

发布于 2022-09-20 16:09:27

82000

代码可运行

文章被收录于专栏：全栈程序员必看全栈程序员必看

运行总次数：0

代码可运行

题目描述： 二进制数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.cn/167889.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

java