UVa 10692 - Huge Mods

// Accepted
// Time: 0.00
// Theory: a ^ ( b % phi[m]) + phi[m]
// suppose, m=53, n=3, and a1=2, a2=3 and a3=2; then: m=53, m1=phi[m]=52, m2=phi[m1]=24;
// we know: 2 ^ 3 ^ 2 % m ; that means it will be 2 ^ 3 ^ 2 ^ 1
// We have to start from the last, so: ans1 = (2 ^ 1 % m2) + m2=26; which is mod(2 , ans, m2), ans=1 here;
// ans2 = (( 3 ^ ans1) % m1) + m1 = 61; which is mod(3 , ans, m1), ans=ans1;
// main_ans = (2 ^ ans2) % m=35; which is mod(2 , ans, m), ans = ans2;
// Good Day... :) Happy Coding

#include<bits/stdc++.h>

using namespace std;

#define high 10010
#define sf scanf
#define pf printf

char ch[high];
int phi[high] , ar[high], br[high];

void Euler_phi()
{
    int i,j;

    phi[1] = 1;

    for(i=2; i<high; i++)
    {
        if(!phi[i])
        {
            phi[i] = i-1;

            for(j=2*i; j<high; j+=i)
            {
                if(!phi[j])
                {
                    phi[j] = j;
                }

                phi[j]/=i;
                phi[j]*=(i-1);
            }
        }
    }

    //for(i=2; i<=10; i++) cout << phi[i] << " ";
}

int mod(int a, int b, int c)
{
    if(!b) return 1;

    if(!(b&1))
    {
        int r = mod(a, b/2, c);
        return ((r%c) * (r%c)) % c;
    }

    else
    {
        return ((a%c) * (mod(a,b-1,c)%c)) % c;
    }
}

int main()
{
    Euler_phi();

    int tc=0;

    while(~sf("%s", &ch))
    {
        if(!strcmp(ch, "#")) break;

        int m = atoi(ch);

        int n;
        sf("%d", &n);

        int i , x , tmp=m;

        sf("%d", &x);
        ar[0] = x;
        br[0] = m;

        for(i=1; i<n; i++)
        {
            sf("%d", &x);
            ar[i] = x;
            tmp = phi[tmp];
            br[i] = tmp;
        }

//        for(i=0; i<n; i++)
//        {
//            cout << ar[i] << " " << br[i] << "\n";
//        }

        int ans = 1;

        for(i=n-1; i>=1; i--)
        {
            ans = mod(ar[i], ans, br[i]);
            ans+=br[i];
            //cout << ans << " ";
        }

        ans = mod(ar[0], ans, br[0]);

        pf("Case #%d: %d\n", ++tc, ans);
    }

    return 0;
}