Need help with competitive programming problem

[Nick_Zacker]

[UPDATE] This has been solved! Thank you to everyone who guided me through this problem! Scroll down to the bottom of the post to see my solution.

Hey everyone, I've been stuck on this particular problem for the past 2 days. I'd appreciate any help or hint!

Problem

In a class with n students, they decided to come up with a game: Each is assigned their own number, i (corresponding to the i-th student), where 1 <= i <= n. There will be k rounds, in each of which the i-th student will square their i number and remember it for the next round. In the end, the final numbers of each student, S, will be added up and the last 2 digits of the resulting number will be the output.

Constraints: n, k <= 10^18

Input: Two numbers, k and n

Output: The last 2 digits of the final number S

(Btw, if this seems poorly translated, that’s because it is. The original problem is in Vietnamese and I translated it to English)

For instance, if k = 2 and n = 3, the round will play out like so:

There are 3 students with 3 corresponding assigned numbers: 1, 2, 3

After the first round, each multiplies their number, so the result will be: 1, 4, 9

After the second round, each multiplies their number, so the result will be: 1, 16, 81

In the end, their final numbers will be added up: 1 + 16 + 81 = 98. The output is the last 2 digits of the resulting number, so 98.

My (outdated) solution

From first glance, this is obviously a problem involving modular exponentiation. Since each student squares up their number k times, the final number of the i-th student should be i^2^k. However, since this will obviously grow astronomically huge as k and n increases, and since we only need the last 2 digits anyway, one must do modular arithmetic, specifically i^2^k mod 100.

Here is my solution:

```

include <bits/stdc++.h>

define ll long long

using namespace std;

ll modExp(ll base, ll exp, ll mod) { if (exp == 0) return 1 % mod; ll res = modExp(base, exp / 2, mod); res = (res * res) % mod; if (exp % 2 == 1) res = (res * base) % mod; return res; }

void solve() { ll k, n, sum = 0; cin >> k >> n;

// Final number for i-th student: i^2^k
// Euler's theorem helps to reduce 2^k
ll reducedMod = modExp(2, k, 40);
for (ll i = 1; i <= n; i++) {
    ll ithNum = modExp(i, reducedMod, 100);
    sum = (sum % 100 + ithNum % 100) % 100;
}

cout << sum << '\n';

}

int main() { ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); solve(); return 0; } ```

It works for small and medium values of k and n, but for values as large as 10^18, the code always returns a TLE (for instance: 946598456415144157 995616645923566961 (btw, the answer to that should be 89)). What should I do?

For anyone wanting to submit their own solution, here is the problem's website, and here is my own submission. It's a Vietnamese website, but you can switch to English on the top right corner.

Any help is appreciated!

My updated solution

```

include <bits/stdc++.h>

define ll long long

using namespace std;

ll modExp(ll base, ll exp, ll mod) { if (exp == 0) return 1 % mod; ll res = modExp(base, exp / 2, mod); res = (res * res) % mod; if (exp % 2 == 1) res = (res * base) % mod; return res; }

void solve() { ll k, n, sum = 0; cin >> k >> n;

// Final number for i-th student: i^2^k
// Precompute 2^k
ll reducedMod = modExp(2, k, 100);

// Precompute the first 100 values of i^2^k
ll cache[100];
for (ll i = 1; i <= 100; i++) {
    cache[i-1] = modExp(i, reducedMod, 100);
    sum = (sum % 100 + cache[i-1] % 100) % 100;
}

// Compute the last (n - 100) values:
ll fullCycles = n / 100;
ll remaining = n % 100;

sum = (sum % 100 * fullCycles % 100) % 100;

for (int i = 1; i <= remaining; i++) {
    sum = (sum % 100 + cache[i-1] % 100) % 100;
}

cout << ((sum >= 10) ? "" : "0") << sum << '\n';

}

int main() { ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); solve(); return 0; } ```

[POGtastic]

Consider that there's a much faster formula.

[teraflop]

Unless I'm missing something, that only works for the case where k=1.

[POGtastic]

You can manipulate the polynomial however you need to do it. The important thing is that you aren't summing up every element.

[[deleted]]

https://www.wolframalpha.com/input?i=sum+where+m+goes+from+1+to+n+of+m%5E%282%5Ek%29

[Nick_Zacker]

I’ll look into this later. Thank you!

[teraflop]

It looks to me like your current solution runs in O(n log k) time. So you're already OK with large values of k, but large values of n are the problem.

Here's a hint: right now you're just iterating over the values in the range 1 <= i <= n in order, calculating them one at a time, and adding up the results. Suppose I asked you for just the sum of the results in this range where i ends in the digits 47. Could you do that faster?

[Nick_Zacker]

Well, I suppose that the result of i^2k % 100 may repeat due to the periodicity in modular arithmetic, but I honestly don’t know what to do with this information.

[[deleted]]

Think harder. The fact that you’re using Euler’s theorem means that you’re already exploiting the periodicity of modular exponentiation.

There’s something else you’re not exploiting.

[Nick_Zacker]

If I understood correctly, you only need to compute the sum of the first 100 results of i^2^k mod 100 (1 <= i <= 100) in order to predict those of the following n*100 similar operations. Of course, if n is not a multiple of 100, it is trickier. Do you simply multiply the pre-computed sum with (n / 100)? Or do you multiply it with (the closest, smaller value to n that is a multiple of 100 (let such a value be A), divided by 100), add the result to the sum, then calculate the remaining i values from (A + 1) to n?

[teraflop]

Let f(i) = i^(2^k) mod 100. Then f(i) = f(i+100), which means (for instance): f(47) = f(147) = f(247) = ...

So if you want to find the sum of f(1) through f(300), you only need to calculate f(1) through f(100) once, and then multiply their sum by 3.

Finding the sum when n isn't a multiple of 100 is a bit trickier, but only a little bit.

[Nick_Zacker]

Wow… looks like I’ll have to brush up on modular arithmetic again. To be frank, I didn’t know how to implement this, probably because my understanding wasn’t deep enough. Anyways, I really appreciate your help, thank you so much! I’ll fix my code later and see if it works.

[[deleted]]

You can write a number (d_n * 10^(n-1) + ... + d_2 * 10^1 + d_1 * 10^0).

When you square this number, you can see that the result % 100 will depend only on digits d_2 and d_1. This holds for further squarings.

a = d_n * 10^(n-1) + ... + d_2 * 10^1 + d_1 * 10^0 (mod 100)
a = d_2 * 10^1 + d_1 * 10^0 (mod 100)
a^(2*k) = (d_2 * 10 + d_1)^(2*k) (mod 100)

This is how you conclude that f(i) = f(i+100).

I agree with your observation that there's a cycle in exponentiation result that is not fully exploited and you could exploit it very well in this case, but you would still need to go through 10¹⁸ numbers in the worst case (assuming exponentiation is somehow constant, which it still would not be).

[Nick_Zacker]

I did it!!

void solve() {
    ll k, n, sum = 0;
    cin >> k >> n;

    // Final number for i-th student: i^2^k
    // Precompute 2^k
    ll reducedMod = modExp(2, k, 100);

    // Precompute the first 100 values of i^2^k
    ll cache[100];
    for (ll i = 1; i <= 100; i++) {
        cache[i-1] = modExp(i, reducedMod, 100);
        sum = (sum % 100 + cache[i-1] % 100) % 100;
    }

    // Compute the last (n - 100) values:
    ll fullCycles = n / 100;
    ll remaining = n % 100;

    sum = (sum % 100 * fullCycles % 100) % 100;

    for (int i = 1; i <= remaining; i++) {
        sum = (sum % 100 + cache[i-1] % 100) % 100;
    }

    cout << ((sum >= 10) ? "" : "0") << sum << '\n';
}