Project Euler #48 in C++

This question is similar to Project Euler #48 but constraints are different:

$$N < 2000000$$

Just in case the link is unavailable, here is the problem statement:

We've to print

$$\left( \sum_{i=1}^N i^i \right) \mod 10^{10}$$

I've tried the following, but I need something faster than that, because the execution time limit is 2s, and this program can only compute values until \$ N=30000\$ (approx) in the given time limit.

#include 
using namespace std;

#define Mod 10000000000

int main() 
{
    int N;
    cin>>N;
    long long Temp,Sum=0;
    for( int ii=1 ; ii<=N ; ii++ )
    {
        if(ii%10==0)
        {
            continue;
        }        
        Temp=1;
        for( int jj=1 ; jj<=ii ; jj++ )
        {   
            Temp*=ii;
            Temp=Temp%Mod;
        }
        Sum+=Temp;
        Sum=Sum%Mod;
    }
    cout<<Sum;
    return 0;
}

I've added

if(N%10==0)
{
    continue;
}

because numbers of form $$ (k10)^{k10}=k^{k10}10^{k10}=k^{k10}10^{k}10^{10} $$ are not at all going to contribute to the answer.

Note: code is compiled using g++ 4.8.2, C++11 mode

Time complexity

Let's have a look at the time complexity of your algorithm.

The bound is: \$N<2\cdot 10^6\$ and we want to compute: \$\left(\sum_{i=1}^N i^i\right)\mod(10^{10})\$.

Naively computing \$i^i\$ like you are doing will require \$\mathcal{O}(i)\$ operations. Computing the sum \$\sum_{i=1}^N i^i\$ will cost you \$\sum_{i=1}^N \mathcal{O}(i) = \mathcal{O}(N^2)\$ operations. Or in other words you're looking at the order of \$N^2 = 10^{12}\$ iterations of your inner loop. Or if every iteration of your inner loop take 10 ns (i.e. about 10 clock cycles on a 1GHz CPU), you're looking at \$10\cdot 10^{-9}\cdot 10^{12}=10^4\$ (\$10\$ cycles, \$10^{-9}\$ seconds per cycle) seconds which is about 3 hours.

However by using Exponentiation by Squaring you can reduce the time to calculate \$i^i\$ from \$\mathcal{O}(i)\$ to roughly \$\mathcal{O}(\log_2(i))\$ meaning that your expected complexity to calculate the sum: \$\sum_{i=1}^N i^i\$ is \$\mathcal{O}(N\log_2(N))\$. For \$N=10^6\$ you're looking at about \$2\cdot 10^7\$ iterations (\$\log_2(10^6)\approx 20\$) which should take our hypothetical computer about \$2\cdot 10^7\cdot 10\cdot 10^{-9}=0.2\$ seconds to compute.

So to fix your performance you need to use a better exponential computation, there are plenty of examples on the web.

Your code

Now to look at your loop:

if(ii%10==0)
    {
        continue;
    }        
    Temp=1;
    for( int jj=1 ; jj<=ii ; jj++ )
    {   
        Temp*=ii;
        Temp=Temp%Mod;
    }
    Sum+=Temp;
    Sum=Sum%Mod;

The ii%10 == 0 optimization gives you maybe 10% speed gain which isn't much. And I say maybe, it depends on if your CPU correctly predicts the branch so it's probably a bit less than 10%. These kind of problems very rarely depend on how you optimize your code, but rather that you have the correct time complexity, see the above.

StackExchange Code Review Q#64626, answer score: 8