需要解释这段代码的含义

Question

需要解释这段代码的含义

3

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

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

where the

1<=i<j<=n

n是用户输入的数字，用来查找(i,j)对的数量。代码运行完美，但这段代码背后的逻辑很难理解。

附注：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;
    }

- user3276435

1

什么是困难的？ 2 ^ j 是一个异或操作，它切换了2位; -1从中减去。 RHS也有类似的操作。％运算符在LHS除以RHS时给出余数。但是，看过代码后，我感到困惑-(2 ^ j-1)％(2 ^ i-1)== 0的问题与所显示的代码有什么关联？那是计算相同结果的另一种方式吗？ - Jonathan Leffler

1

@JonathanLeffler OP几乎肯定是在那个条件中使用“^”（这不是C代码）来表示指数。 “那是计算相同结果的另一种方式吗？”-- OP说：“代码输出满足条件的（i，j）对的数量...”-- 这是一个清晰的陈述关系。 - Jim Balter

Prateek：最好询问编写代码的人。他们可能会提供一个数学文章，证明这个解决方案适用于给定的问题。证明这样的解决方案并不容易。 - Jim Balter

2

它是一个变量，允许用户一次输入多个数字。最好的方法是只要scanf成功读取'n'，就循环执行。 - Jim Balter

使用所有警告和调试信息编译您的程序（gcc -Wall -g）。考虑 scanf 的返回值（它是成功扫描项目的数量）。请使用调试器（gdb）。 - Basile Starynkevitch

3个回答

4

这是一个非常有趣的问题。如果您尝试一些小的输入，您将对代码有一个大致的了解。

当n = 10时，我使用了一个非常简单的代码来生成所有有效的对，下面是我的结果：

惊讶吗？我们可以看到一个非常明显的模式：当 i，j 满足 j = k * i，其中 k 是一个整数且 j = k * i < n 时，i，j 就是一个有效的配对。这完全与原方程无关，仅取决于 n。

实际上这并不惊讶，因为 (2^(nk) - 1) = ((2^k)^n - 1) = (a^n - 1)，其中 a = 2^k，因此我们可以应用因式分解规则，得到 (a^n - 1) = (a - 1)(a^(n - 1) + a^(n - 2) + .. + 1)，因此可以被 (a - 1) 分解，即 (2^(nk) - 1) % (2^k - 1) == 0。

现在问题变成了如何高效地计算这个数字。根据条件，我们有 j > i。前面我们知道 j = k * i。因此，k 必须在范围内 [2, n / i]。对于每个 i，我们有 (n / i) - 2 + 1 = (n / i) - 1 个有效的 k 选择。因此，总有效配对数将为 sigma((n / i) - 1, 1 <= i <= n)。

至于如何将方程转换为您给出的代码，请参考@MOehm的答案。

- nevets

啊，非常好！你找到了我只看到但无法解释的模式的解释。现在非常明显了。 - M Oehm

@MOehm 我认为我们使用不同的方法得出了相同的解决方案 :) - nevets

1

变量i从1到nrt工作，其中nrt是n的平方根，显式转换为int值。每次循环运行时，sum会加上(n/i)的结果。然后代码打印ans（长类型），其计算方式为（两倍的sum-nrt平方-n）。

- h8pathak

3

OP询问为什么这个计算能得出所期望的结果。 - Jim Balter

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- M Oehm · Accepted Answer

让我们采取暴力解决问题的方法并打印结果*：

 #############################   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 - 1 替换 (n - i) / i，并将共同的减数 -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

我们可以从右往左看，并计算每个加数出现的次数，得到相同的总和。

∑(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))

这其实只是另一种写求和式的方式；你可以通过重新分组，使它们共享相同的分母来看出这一点：

∑(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语言爱好者。

**) 我不知道这个模式为什么存在。可能有一个合理的解释，但现在我相信我的模式匹配技能。盲目地。编辑@nevets的答案中有关于这个模式的解释。