Cod sursa(job #635411)
Utilizator | Antoanela Siminiuc antoanela | Data | 19 noiembrie 2011 11:16:00 |
---|---|---|---|
Problema | Ciuperci | Scor | 30 |
Compilator | cpp | Status | done |
Runda | .com 2011 | Marime | 0.47 kb |
#include <cstdio>
#define mod 666013
#define ll long long
int q;
ll n;
ll solve (ll n)
{
if (n==1) return 1;
if (n==2) return 2;
n--;
ll x, y=n/2;
if (n&1)
{
x=solve(y);
y=solve(y+1);
return (2*x*y)%mod;
} else
{
x=solve(y);
return (x*x)%mod;
}
}
int main()
{
freopen("ciuperci.in","r",stdin);
freopen("ciuperci.out","w",stdout);
scanf("%d", &q);
while (q--)
{
scanf("%lld", &n);
printf("%lld\n", solve(n));
}
}