首页 > 技术文章 > 关于求mod运算

lonelytree 2013-07-16 15:41 原文

  问题描述:有个同事让我求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,搞定。

推荐阅读