小易喜欢的数列

import java.util.Scanner;

public class Main {
    //动态规划 dp[i][j]表示的含义是前i个整数，以j结尾的时候，有多少喜欢的数列。
    //转义方程如下
    //dp[i][j]=sum( dp[i-1][1,2,3,…,k] ) - sum(dp[i-1][x] , x>j且 x%j=0)

    public static final int M = 1000000007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        sc.close();
        System.out.println(Count(n, k));
    }
    public static int Count(int n, int k){
        //dp[j][j]表示前i个整数以j结尾时，有多少喜欢的队列
        //这里数组的下标不从0开始
        int [][]dp = new int[n+1][k+1];

        //这个没有意义，只是为了计算dp[1][k],即当只有一个数时借助前面的状态来计算
        dp[0][1] = 1;
        for(int i = 1 ; i <= n ; i++){

            int sumAll = 0;
            //先算 sum( dp[i-1][1,2,3,…,k] )
           for(int j = 1 ; j<= k; j++){
               //这里的j就是上面的k。 由于dp[0][1] = 1,当i=1时，可以得出正确结果1
               sumAll = sumAll + dp[i-1][j];
               //这里每次都要跟M取模，否则可能会产生整数溢出
               sumAll = sumAll%M;
           }
           //接下来算不符合的部分
            //sum(dp[i-1][x] , x>j且 x%j=0)
            //当以j结尾时，
            for(int j = 1 ; j <= k; j++){
                int sumNo = 0;
                //这里包含两个意思 即 x > j 且 x%j=0
                for(int x = j + j ; x <= k ; x+=j){
                    sumNo += dp[i-1][x];
                    sumNo %= M;
                }
                //dp[i][j]=sum( dp[i-1][1,2,3,…,k] ) - sum(dp[i-1][x]x>j且 x%j=0)
                dp[i][j] = (sumAll - sumNo + M)%M;

            }

        }
        int result = 0;
        for(int i = 1; i <= k; i++) {
            //计算n个数分别以1-k结尾的符合数列
            result+=dp[n][i];
             result %= M;
        }
        return  result;

    }
}

	

# python 代码时间复杂度只能过 90%，哪里还可以改进呢？

# dp[i][j] 代表，长度为 i，以 j 结尾的满足条件的数列的个数
# dp[i][j] = sum(dp[i-1][1~k]) - sum(dp[i-1][x]), 其中 x>j and x%j==0
# ps: 对同一个 i, sum(dp[i-1][1~k]) 是不变的
# 1<=i<=n, 1<=j<=k
def find(n, k):
    MOD = 1000000007
    dp = []
    for i in range( n +1):
        dp.append([0 for j in range( k +1)])
    for i in range(1, n+ 1):
        # i=1时，dp[1][j] = 1
        if i == 1:
            for j in range(1, k + 1):
                dp[i][j] = 1
        else:
            # 计算对同一个 i，sum1 都相同
            sum1 = 0
            for x in range(1, k + 1):
                sum1 += dp[i - 1][x]
                sum1 %= MOD
            # 计算对每一个j 都不同的第二个 sum部分
            for j in range(1, k + 1):
                sum2 = 0
                # 如果不用 while用下面  for 循环，只能过40%
                x = 2 * j
                while x <= k:
                    sum2 += dp[i - 1][x]
                    sum2 %= MOD
                    x += j
                # for x in range(j + 1, k + 1):
                #     if x % j == 0:
                #         sum2 += dp[i - 1][x]
                #         sum2 %= MOD
                
                # 因为前面都对sum1/sum2 做了mod处理，可能sum1比sum2小
                # 所以先给 sum1 加一个 MOD
                dp[i][j] = (sum1 + MOD - sum2) % MOD
    # 注意结果不是 dp[n][k]，而是sum(dp[n][1~l])
    res = 0
    for j in range(1, k + 1):
        res += dp[n][j]
        res %= MOD
    return res


if __name__ == "__main__":
    n, k = map(int, input().strip().split(" "))
    print(find(n, k))

	
import java.util.Scanner; public class Main2 { public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] s = scanner.nextLine().split("0t");
        Integer n = Integer.valueOf(s[0]);
        Integer k = Integer.valueOf(s[1]); int[] a= new int[n]; getsum(n,k);
        System.out.println(sum%q);

    } public  static  int q=1000000007; public static int sum=0; public static void getsum(int n,int k){

  int[] a= new int[n]; aa(a,0,n,k);
    } public static void aa(int[] a,int index,int n,int k){  if(index>=n){ //如果已经有n个数满足，总数加1  sum++;
   return ;
} 

 for(int i=1;i<=k;i++){ //循环从1-k中取数

 if(index==0){
                    a[index]=i; 

 aa(a,index+1,n,k);//第一个数不用比较，直接添加 求下一位
                }else{ 

 if(a[index-1]<=i||a[index-1]%i!=0){//满足要求的就 加入，求下一位数
                        a[index]=i; aa(a,index+1,n,k);
                    }
                }
            } return;
    }
}