需要解释此代码

Question

代码输出满足条件的(i,j)对的数量

(2^j-1) % (2^i-1) == 0

在哪里

1<=i<j<=n

n是用户输入的数字,在该数字下将找到(i,j)对的数量.代码工作得很好,但这段代码背后的逻辑很难理解.

PS:t是一个变量,它允许用户一次输入多个数字.

    #include<stdio.h>
    #include<math.h>
    int main()
    {   
        int t;
        long n,sum,ans; 
        scanf("%d",&t);
        while(t--)
        {
            scanf("%ld",&n);
            int nrt=(int)sqrt(n);
            sum=0;
            for(int i=1;i<=nrt;i++)
            {
                 sum+=n/i;
            }
            ans=2*sum-nrt*nrt-n;
            printf("%ld\n",ans);
        }
    return 0;
    }

Answer 1

让我们采用蛮力的方法解决问题并打印结果*:

 #############################   2^^1 -1 == 1
  -#-#-#-#-#-#-#-#-#-#-#-#-#-#   2^^2 -1  == 3
   --#--#--#--#--#--#--#--#--#   2^^3 -1  == 7
    ---#---#---#---#---#---#--   2^^4 -1  == 15
     ----#----#----#----#----#   2^^5 -1  == 31
      -----#-----#-----#-----#   2^^6 -1  == 63
       ------#------#------#--   2^^7 -1  == 127
        -------#-------#------   2^^8 -1  == 255
         --------#--------#---   2^^9 -1  == 511
          ---------#---------#   2^^10 -1 == 1023
           ----------#--------   2^^11 -1 == 2047
            -----------#------   2^^12 -1 == 4095
             ------------#----   2^^13 -1 == 8191
              -------------#--   2^^14 -1 == 16383
               --------------#   2^^15 -1 == 32767
                --------------   2^^16 -1 == 65535
                 -------------   2^^17 -1 == 131071
                           ...   ...

哈希标记表示满足条件的情况.一个很好的模式出现了:你的每个数字都可以被1整除,每个数字都可被3整除,每三个数字可以被7整除,依此类推.每个i数字都可被整除2^^i - 1.**

有了这种洞察力,我们可以将您的功能编码为:

int f(int n)
{
    int sum = 0;
    int i;

    for (i = 1; i <= n; i++) sum += (n - i) / i;

    return sum;
}

我们可以替代(n - i) / i使用n / i - 1和移动共同减数-1到返回值:

int g(int n)
{
    int sum = 0;
    int i;

    for (i = 1; i <= n; i++) sum += n / i;

    return sum - n;
}

现在让我们来看看总和?(1, n: n / i).例如:

?(i = 1, 9: 9 / i) = 9 + 4 + 3 + 2 + 1 + 1 + 1 + 1 + 1

我们可以通过从右到左查看它并计算每个summand出现的频率来获得相同的总和:

?(i = 1, 9: 9 / i) = 5*1 + 1*2 + 1*3 + 1*4 + 1*9

我们可以轻松获得这种表示:

?(i = 1, n: n / i) = ?(1, n: i * (n / i - n / (i + 1))

这真的只是写这笔钱的另一种方式; 你可以通过不同的方式对summands进行分组,以便它们共享相同的分母:

?(i = 1, N: i * (n / i - n / (i + 1))
    = n + ?(i = 1, n: ((i + 1) - i)  * n / (i + 1))
    = n + ?(i = 1, n: n / (i + 1)) - (N + 1) * (n / (N + 1))
    = n + ?(i = 2, n + 1: n / i) - c
    = ?(i = 1, n: n / i) - c

附加项c = (N + 1) * (n / (N + 1))是一个修正项,因为只使用了一半的项i = n + 1.在整个范围内求和时,n / (n + 1)为零并消失.当仅对数组的一部分求和时,它不会消失,我们稍后会看到.

如果我们将总和分成头和尾s = sqrt(n),我们得到:

?(i = 1, n: n / i) = ?(i = 1, s: n / i) + ?(s + 1, n: n / i)

让我们以原始的方式表示头部,并以"计数加数"的方式表示尾部,例如:

?(i = 1, 9: 9 / i) = (9 + 4 + 3)   +   (5*1 + 1*2)

任何n:

?(i = 1, n: n / i) 
    = ?(i = 1, s: n / i) + ?(1, s - 1: i * (n / i - n / (i + 1))
    = ?(i = 1, s: n / i) + ?(1, s: n / i) - s * (n / s)

所有的划分都是整数除法(这就是为什么有时必须有括号)n / s == s,所以:

?(1, n: n / i) = ?(i = 1, s: n / i) + ?(i = 1, s: n / i) - s * (n / s)
               = 2 * ?(i = 1, s: n / i) - s²

这产生了你原来的功能:

int h(int n)
{
    int nrt = sqrt(n);
    int sum = 0;
    int i;

    for(i = 1; i <= nrt; i++) sum += n/i;

    return 2 * sum - nrt * nrt - n;
}

其中?(1, n: n / i)在g上述已被替换2 * ?(i = 1, s: n / i) - s².

*)我在这里偷了D的力量算子 ^^,以免混淆那些^以面值为特征的旧C buff ,即xor.

**)我不知道,为什么模式显示.可能有一个很好的解释,但就目前而言,我相信我的模式匹配技能.盲目.编辑 @ nevets的答案有这种模式的解释.