Getting a TLE but can’t debug it

  c++

Description

A sequence is called good if each number is divisible by the next number in the sequence. You have to find the number of good sequences with length K containing positive integers ≤ N.

Since the answer can be large, print it 109 + 7.

Input Format

The first line of the input contains one integer T – the number of test cases. Then T test cases follow.

The first and only line of each test case contains two space-separated integers N, K.

Output Format

For each test case, print the number of good sequences with length K containing positive integers ≤ N. Since the answer can be large, print it 109 + 7.

Constraints

1≤ T ≤ 400000

1≤ N, K ≤ 2000

#include<bits/stdc++.h>
using namespace std;
#define int long long

int n,k;
int mod=1000000007;
int dp[2500][2500],sum1[2500][2500];
vector<vector<int>> fact(2500);

void factors(){
    for(int i=1;i<2500;i++){
        for(int j=1;j*j<=i;j++){
            if(i%j==0){
                if(j*j==i){
                    fact[i].push_back(j);
                }
                else {
                    fact[i].push_back(j);
                    fact[i].push_back(i/j);
                }
            }
        }
    }
}

int rec(int max_no,int len){
    if(len==1) return dp[max_no][len]=1;
    if(dp[max_no][len]!=-1){
        return dp[max_no][len];
    }
    int sum=0;
    for(auto i:fact[max_no]){
        sum=(sum+rec(i,len-1))%mod;
    }
    return dp[max_no][len]=sum;
}

int rec1(int max_no,int len){
    if(max_no==1) return rec(max_no,len);
    if(sum1[max_no][len]!=-1) return sum1[max_no][len];
    return sum1[max_no][len]=(rec1(max_no-1,len)+rec(max_no,len))%mod;
}

void solve(){
    cin>>n>>k;
    int sum=0;
    for(int i=1;i<=n;i++){
    sum=(sum+rec(i,k))%mod;
    }
    cout<<rec1(n,k)<<"n";
    
   
} 

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    factors();
    for(int i=0;i<2500;i++){
        for(int j=0;j<2500;j++){
            dp[i][j]=-1;
            sum1[i][j]=-1;
        }
    }
    int t;cin>>t;while(t--)
    solve();
    
}

I am getting a TLE . But don’t know why?
How can I optimize my code?

Source: Windows Questions C++

LEAVE A COMMENT