pypy3 解法, 执行用时: 179ms, 内存消耗: 29520K, 提交时间: 2023-07-19 16:48:07

n,k=map(int,input().split())
mod=10**9+7
f=[0]+[1]*k

for _ in range(n-1):
    total=sum(f)%mod
    nf=[0]*(k+1)
    for i in range(1,k+1):
        if i==1:
            nf[i]=1
        else:
            nf[i]=total
            c=2
            while c*i<=k:
                nf[i]=(nf[i]-f[c*i]+mod)%mod
                c+=1
    f=nf
    #print(f)
print(sum(f)%mod)

            
            
            
    

C++14(g++5.4) 解法, 执行用时: 54ms, 内存消耗: 4156K, 提交时间: 2020-08-11 14:12:42

#include<cstdio>
using namespace std;
const int N=20,M=100005,P=1000000007;
int n,m;
int f[N][M];
int s[N];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) f[1][i]=1;
	s[1]=m;
	for(int i=2;i<=n;i++){
		s[i]=0; 
		for(int j=1;j<=m;j++){
			f[i][j]=s[i-1];
			for(int k=j+j;k<=m;k+=j){
				f[i][j]=(f[i][j]-f[i-1][k])%P;
			}
			s[i]=(s[i]+f[i][j])%P;
		}
	}
	printf("%d",s[n]);
	return 0;
} 

C++11(clang++ 3.9) 解法, 执行用时: 38ms, 内存消耗: 4252K, 提交时间: 2020-08-24 16:13:38

#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
int dp[11][100010];
int main()
{
	int n,k;
	int i,j,p,t,sum=0,m;
	cin>>n>>k;
	for(i=1;i<=k;i++)
	{
		dp[1][i]=1;
		sum+=dp[1][i];
	}
	for(i=2;i<=n;i++)
	{
		p=sum;
		sum=0;
		for(j=1;j<=k;j++)
		{
			t=p;
			for(m=2*j;m<=k;m=m+j)
			t=(t-dp[i-1][m])%MOD;
			dp[i][j]=t;
			sum=(sum+t)%MOD;
		}
	}
	cout<<sum;
	return 0;
}

Python(2.7.3) 解法, 执行用时: 1824ms, 内存消耗: 9688K, 提交时间: 2019-07-12 16:15:11

import sys
line = sys.stdin.readline().strip()
esp = 1000000007
n,k = [int(i) for i in line.split(" ")]
count = [1] * (k+1)
count[0] = 0
res = k
for i in range(n - 1):
    for j in range(2, k+1):
        count[j] = res
        for l in range(j * 2, k+1, j):
            count[j] -= count[l]
    res = sum(count) % esp
print res