TLE - Powerful sum

general
, , ,
1

My C++ code is having TLE… even though I did all I know to make it faster include using standard I/O routines:

#include <cstdio>
using namespace std;

unsigned long long int mod_pow(int b, int exp, int mod)
{
    unsigned long long int c = 1;
    for(int a = 1; a <= exp; a++)
    {
        c = (c*b)%mod;
    }
    return c;
}

int main()
{
    int t;
    scanf("%d", &t);
    for(int x = 0; x < t; x++)
    {
        unsigned long long int ans = 0;
        int n, k, modulus;
        scanf("%d%d%d", &n,&k,&modulus);
        for(int u = 1; u <= n; u++)
        {
            ans += mod_pow(u,k,modulus);
        }
        printf("%d\n", ans%modulus);

    }
    return 0;

}

Can someone give me a hint? Thanks in advance

2

Your solution is O(k*n) what’s for k = 100 and n = 10^9 too slow (no problem with I/O). You have to find better (quicker) algorithm.