大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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账号...