小编use*_*435的帖子

代码输出满足条件的(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;
    }

在为我的期末考试练习时,我在J. Hopcroft,R.Motwani,J.Ullman,第222页的自动机理论,语言和计算中发现了这个问题.

PDA应该接受其中1的数量是0的数量的两倍的字符串,并且如果我没有误解问题,则字符串可以具有不同的0和1的序列,没有特定的模式或特定的顺序.

我解决这个问题的第一个方法是将问题分成两部分

1. 用于从0开始的字符串的PDA.(例如 - 010111)
2. 用于以1开头的字符串的PDA.(例如 - 110101)

但划分问题似乎并没有降低问题的复杂性.

这些问题的解决方法是什么？