this is my code. which gets me WA.
Any help would be greatly appreciated
thx

#include <stdio.h>

int main()
{
    long a,b,c,d,e,f,g,state,i,n,m,y;
    scanf("%d %d %d", &n,&m,&y);
    state = 0;
    for (i=0; i < m; i++)
    {
        e = i % m;
        d = e;
        for (c=1; c< n; c++) d *= e;
        d %= m;
        if (d == y)
        {
            if (state == 0)
            {
                printf("%d", i);
                state = 1;
            }
            else if (state) printf(" %d",i);
        }
    }
    if (!state) printf("-1\n");
    return 0;
}

for (c=1; c< n; c++) d *= e;

Here d > 2^32 - 1, so WA.
Even more, if you'll correct this program you'll get TL, since
there's a faster way to do x^n (mod y)

> for (c=1; c< n; c++) d *= e;
>
> Here d > 2^32 - 1, so WA.
> Even more, if you'll correct this program you'll get TL, since
> there's a faster way to do x^n (mod y)

ic... i managed to get AC with d = d * e % m;
however, im interested in the faster way to do x^n mod y..could you
show me how?

See this fact...
x^n (mod y) = (x^(n/2) (mod y)) * (x^(n/2) (mod y))
if n is even, otherwise add in the sentence above: * x (mod y)
You can do it in O(log N)

you are very clever~but this problem seems to be so week
the code below is enough
for i:=1 to n do
  begin
     sum:=sum*x;
     sum:=sum mod m;
  end;

You don't get any satisfaction by solving with brute force, even if it happens to work

This is how i implemented my pow function for this problem.
O(lg n) time.

typedef long long ll;

ll pow(ll a, int n, int m)
{
    if(n==0)
    return 1;
    ll temp=pow(a, n/2, m)%m;

    if(n%2)
    return ((a*temp%m)*temp%m);
    return temp*temp%m;
}

int pow(int a, int n, int p)// a ^ n mod p
{
  int r = 0;
while (n)
{
  if(n % 2 == 1)
    r = r * a % p;
   a = a * a % p;
  n /= 2;
}
  return r;
}

by the way problem is much more simpler
    A[1]=somenumber; // sn
    A[2]=sn;
    A[3]=sn;
    int i;
    for (i=sn;i<=sn;i++)    A[i]=A[i-sn]+A[i-sn]+sn;
    int N;
    scanf("%i",&N);
    printf("%i",A[N]);

Edited by author 29.11.2007 09:17