Help Me Pleaseeeeee

Problem Link: https://mirror.codeforces.com/problemset/problem/700/E

My Submission: https://mirror.codeforces.com/problemset/submission/700/366419085

Can anyone tell me where I'm going wrong? What should I do to accept this problem? I can't find any editorial for this problem.

Why Coin Combinations II problem in CSES geting TLE by recursive solution? but iterative solution in accepted.

My recursive code is here:

#include<bits/stdc++.h>
using namespace std;
// #define int long long
int n, m, p, mod=1e9+7, ans=0; vector<vector<int>>dp(110, vector<int>(1e6+9, -1));
vector<int>v;
int ok(int p, int i){
  // cerr<<p<<'\n';
  if(p==0) return 1;
  if(p<0 || i==n) return 0;
  if(dp[i][p]!=-1) return dp[i][p];
  int k=0;
  k=(k+ok(p-v[i], i)); if(k>mod) k-=mod;
  k=(k+ok(p, i+1)); if(k>mod) k-=mod;
  return dp[i][p]=k;
}
int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin>>n>>m; v.resize(n); for(int i=0; i<n; i++) cin>>v[i]; //sort(v.begin(), v.end());
  cout<<ok(m, 0)%mod<<'\n';
}

Divisor Sieve — Efficiently Finding Divisors of Numbers

Finding the divisors of a number efficiently is a crucial operation in number theory and competitive programming. The Divisor Sieve algorithm allows us to compute the divisors of all numbers up to N in O(N log N) time. In this blog, we will discuss its working, implementation, and applications.

Understanding the Divisor Sieve

The goal of this sieve is to precompute the divisors of every number up to N efficiently. Instead of iterating through all numbers to find their divisors separately, this sieve approach allows us to systematically determine the divisors of all numbers in a structured and optimized way.

By leveraging a sieve-based approach, we ensure that each number's divisors are found in a much faster manner compared to naive methods. This makes the Divisor Sieve particularly useful for problems requiring frequent divisor queries.

How Does It Work?

1. Iterate over all numbers i from 1 to √N.
2. For each multiple j of i, store i as a divisor of j.
3. Additionally, store j/i as a divisor if it is different from i (to avoid duplicate storage for perfect squares).

The sieve ensures that every number gets all its divisors efficiently without iterating through all numbers separately.

Using the Logic of the Sieve of Eratosthenes

The Divisor Sieve is inspired by the Sieve of Eratosthenes, a well-known algorithm for finding prime numbers efficiently. The key similarity is that instead of marking numbers as prime or composite, we store divisors for each number. Just like the Sieve of Eratosthenes marks multiples of primes, the Divisor Sieve processes multiples of each integer, ensuring that all divisors are computed efficiently. This approach significantly reduces the time complexity compared to brute-force methods.

---

Time Complexity Analysis

• The inner loop runs for every multiple of i, giving an overall complexity of O(N log N).
• This is much faster than checking each number individually, which would take O(N√N).

---

Implementation in C++

Here is the C++ implementation of the Divisor Sieve:

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

const int N = 1e6;  // Maximum limit
vector<int> d[N];

void divisorSieve() {
    for (int i = 1; i * i < N; i++) {
        for (int j = i * i; j < N; j += i) {
            d[j].push_back(i);
            if (j / i != i) d[j].push_back(j / i);  // Avoid duplicate for perfect squares
        }
    }
}

int main() {
    divisorSieve();
    int num = 36;
    cout << "Divisors of " << num << ": ";
    for (int div : d[num]) cout << div << " ";
    cout << endl;
    return 0;
}

---

Applications of the Divisor Sieve

1. Finding Divisors of Numbers efficiently up to N.
2. Counting the Number of Divisors for each number in O(1) after precomputing.
3. Sum of Divisors by maintaining an additional sum array.
4. Finding Perfect Numbers, Amicable Numbers, and other mathematical properties.
5. Optimizing Factorization Problems by leveraging precomputed divisor lists.

Final Thoughts

The Divisor Sieve is an essential technique for efficiently computing divisors in number-theoretic problems. By leveraging the logic of the Sieve of Eratosthenes, we achieve a much faster and more scalable approach compared to brute-force methods. This makes it a valuable tool in competitive programming and mathematical problem-solving.

If you have any suggestions or questions, feel free to comment below! Happy Coding!

Hi Codeforces :) Recently I've reached Specialist and am looking for to reach Expert. So I want some advice from you if you have reached Expert or more, like what topics should I focus on, websites to practice on and some references that may help.

Thank you anyway..