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

二进制除法_111011001÷1011二进制除法题目描述: 二进制数nmodm的结果是多少?对于二进制数的取模运算,我们的第一反应一定是模拟其减法运算,然后逐位相减。但是这道题的数据达到了$2e5$,鉴于减法模拟的巨大常数,一定是会

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

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;
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/167889.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号