问题描述:有个同事让我求x=[0,10^7]中满足xmod100和mod101的x有哪些。
思路:
1、刚开始想都没想,x%100 == x%101,遍历所有的x。
2、写完之后想了想如何优化下(纯属闲的蛋疼),首先转换成数学公式:
x=k1*100+r1,x=k2*101+r2,因为要r1和r2相等。那么显然r=min(r1,r2),即r最大为99.
那么k1*100+r = k2*101+r,消除r为:k1*100=k2*101,要使得这个成立,那么k1满足n*101,k2同理。
那么此时x可以转换为:x=n*101*100+r,我们知道x最大值为10^7,r最小值为0,那么我们就可以求出n的最
大值:990,也就是n的范围是n=[0,990],r=[0,99].
首先可以求出两个关键的数据:a).满足的最大x ; b).满足这样的x的个数.
max_x = 990*101*100+99;
count_x = 991*100;(其中991为n的个数0~990,100为r的个数0~99)
那么要求所有的x,也很简单:两层循环n&r,搞定。