时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld
题目描述
众所周知,某个被共青团点名的学校的机房里有一个蒟蒻,名字叫做clccle,因为文化课成绩不好而经常被班主任gank,这次他遇到了一个很困(rui)难(zhi)的数学题,因为clccle非常辣鸡,所以他想到了聪明的你,你能帮Ta解决这个问题吗?
给定两个整数N,M,表示区间 [2^N,2^M),请求出在这个区间里有多少个整数i满足i % 7=1
输入描述:
一行,两个整数N,M 0<=N<M<=65
输出描述:
一个数字ans,表示满足条件的数字的个数
示例1
输入
2 3
输出
0
说明
在区间[2^2,2^3 )里满足条件的整数的个数为零 ,(4,5,6,7,8因为在开区间边界上所以不做考虑)
#include<iostream> #include<math.h> using namespace std; int main() { int n,m; long long ans = 0; cin >> n >> m; long long minnum = pow(2,n); long long maxnum = pow(2,m); long long remaindermax = maxnum / 7; long long remaindermin = minnum / 7; long long num = remaindermax - remaindermin; if(minnum % 7 == 1) { ans++; } if(maxnum % 7 == 1) { ans += num - 1; } else { ans += num; } cout << ans; return 0; }
可能对于大多数人来说第一想法是要创建一个for循环用循环区间内数值都来对7取余,但是注意条件所涉及的范围非常的大,如果对数进行遍历操作的话就会非常浪费时间
。
然后我就想了一种情况,对操作数用7进行取模操作如果余数为1那么每增加一个7就会使余数也为1,按照这个思路我就设计了最多有几个余数为1的情况。也就是上面所定义的num,而且题目所设定的区间为左闭右开区间,所以通过在纸上模拟计算发现如果范围的最小值即左端点的值除以7为1的话,那么定义的满足条件的数就要加1。如果右端点值对7取模余数为1的话,那么满足条件的数就要减1;
之后返回满足条件的值