F - Modular Exponentiation
2024-08-31 03:48:36
Problem description
The following problem is well-known: given integers n and m, calculate 2n mod m,
where 2n = 2·2·...·2 (n factors), and x mod y denotes the remainder of division of x by y.
You are asked to solve the "reverse" problem. Given integers n and m, calculate m mod 2n.
Input
The first line contains a single integer n (1 ≤ n ≤ 108).
The second line contains a single integer m (1 ≤ m ≤ 108).
Output
Output a single integer — the value of m mod 2n.
Examples
Input
4
42
Output
10
Input
1
58
Output
0
Input
98765432
23456789
Output
23456789
Note
In the first example, the remainder of division of 42 by 24 = 16 is equal to 10.
In the second example, 58 is divisible by 21 = 2 without remainder, and the answer is 0.
解题思路:由于给出的m最大值为108,于是暴力找出2k>108时的最小值k,解得k=27,所以只要n>26,直接输出m(取模一个比自己大的数字,结果为本身),反之直接取模运算,这样就不会发生数据溢出。(位运算是个好东西,长记性了)
AC代码:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
cout<<(n>?m:m%(<<n))<<endl;
return ;
}
最新文章
- OpenMesh 将默认的 float 类型改为 double 类型
- 剑指offer编程题java实现(正在更新)
- 柯朗数(Courant number)研究
- js基础-表单验证和提交
- 通过nsenter连接docker容器
- Android studio 自定义打包APK名称
- 手机前端页面js
- 用SQL语句修复SQL Server数据库
- Asp.net弹出层并且有遮罩层
- Mysql之二
- SQL操作(增删改查)
- 【解决】hive动态添加partitions不能超过100的问题
- 设置MySQL数据表主键
- C#基础知识回顾--线程传参
- Redis + keepalived 高可用群集搭建
- 基于epoll实现简单的web服务器
- 网站内容禁止复制和粘贴、另存为的js代码
- Linux下安装 Python3
- 《Java》第三周学习总结 20175301
- 微信自定义菜单errcode(40016)
热门文章
- SpringMVC进行json数据交互
- Uedior上传大文件超时报错
- 如何反向遍历List集合
- 渗透实战(周二):FLUXION暴力破解WIFI登录口令
- Thesis Viva checklist
- NOD 1113矩阵快速幂
- PAT 1119 Pre- and Post-order Traversals
- [Bzoj3940] [AC自动机,USACO 2015 February Gold] Censor [AC自动机模板题]
- linux -- 视频尺寸-cif、2cif、dcif、D1、HD1、4D1
- hdu_1038_Biker&#39;s Trip Odometer_201311021643