Pekiban orz will win info(1)cup!

orz only 100 on Problem 6

Sorry for not meeting your expectations :)

I'll do my best in order to make this untrue.

Akeed ya3ny mesh m7taga

Bro, you are Aldk, not me

why? they are at top but from the bottom

what?

absolute cinema

I feel bad for Akhmed ;(

here

For day2B, let's look at the equation:

a[1] + a[2] + .. + a[K] = N

Notice that all the elements are divisible by a[1], so N must be divisible by a[1]. Let N = a[1] * x.

Divide the equation by a[1]:

1 + a[2] / a[1] + a[3] / a[1] + .. + a[K] / a[1] = N / a[1]

Let b[i] = a[i+1] / a[1] for i from 1 to K-1.

b[1] + b[2] + .. + b[K-1] = x-1

Notice that this equation is the same thing but with different N and smaller K.

Now let dp[N][K] be the number of ways to make the sum N out of at most K terms.

We have dp[N][K] = dp[N][K-1] + sum(dp[x-1][K-1]), where x can be any divisor of N, including N.

Now, notice that we do not need the K dimension, because we need to get the sum of all dp[N][K] (for a fixed N, of course) and we do not care how large K is.

So we have an even more simplifed recurrence: dp[N] = sum(dp[x-1]), where x is a divisor of N. This can be computed easily using a sieve.

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 500000;
const int MOD = 1000000007;

int dp[MAXN + 1];

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  dp[0] = 1;
  for(int i = 1; i <= MAXN; i++) {
    for(int j = i; j <= MAXN; j += i) {
      dp[j] += dp[i - 1];
      if(dp[j] >= MOD) {
        dp[j] -= MOD;
      }
    }
  }
  
  int t;
  cin >> t;
  while(t--) {
    int n;
    cin >> n;
    cout << dp[n] << "\n";
  }
  
  return 0;
}

You are doing the right thing, but at sweep line you need to have a DS that solves the prefix queries in O(1). You can use SQRT Decomposition.

Here is my submission.

I think you can divide the problem into finding the sum in a range of numbers smaller than M and sum of numbers over M to do that you can process queries in offline by sorting the queries in decreasing order of M