Competitive Programming Solutions

1476A - K Divisble Sum

29 Jan 2021 — Tags: math — URL

Assume $k \geq n$, otherwise find the smallest multiple of $k$ that matches that condition.

We shall fill the $n$ elements with $floor(k / n)$ and then displace uniformly the remainder over all posible $a_i$. In this way the remainder counts for at most $1$.

Time complexity: $O(1)$

Memory complexity: $O(1)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int ceil(int a, int b) { return (a + b - 1) / b; }
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n, k;
        cin >> n >> k;
        k *= ceil(n, k);
        cout << k / n + ((k % n) != 0) << endl;
    }
    return 0;
}

Related posts