V#
# include <iostream>
#
# include <cstdio>
#
using namespace std;
#
int NZD(int x,int y)
#
{
#
if (y==0) return x;
#
return NZD(y,x%y);
#
#
}
#
long long n,a,i,k;
#
#
int main ()
#
{
#
k=0;
#
scanf ("%lld",&n);
#
for (a=1;a<=n;a++)
#
if (NZD(n,a)==1) k++;
#
printf("%lld",k);
#
return 0;
#
}
Pomoc!!! Prodje 13/20 test primjera a na ostalima istekne vrijeme! Da li se moze ispraviti sta u kodu, ili druga ideja!!!
ne moze ti proci, jer pogledaj koliko moze biti n 1 000 000 000 000, a komp za sekundu moze da uradi otprilike 25 000 000 operacija ... tako da for (int a = 1; a <= n; a++) puca na vremenu ...
ovde ide princip ukljucenja iskljucenja ...
razmisli kako da resis ovo sa prostim brojevima do korena iz n ...
ako treba jos pomoci pitaj ...
samo 25m ? Pa gde ti zivis bre :) Mislim da na z-u moze i 100m+ operacija u sekundi...
A sto se tice zadatka, posto je ovo sto se trazi zapravo ojlerova f-ja, moze da se upotrebi formula za racunanje iste :)
kako gde ...
negde moze 25M, a negde preko 100M ...
ali mislim da je na z-treningu oko 25M, mozda do 50M ...
i nije ti svejedno koje operacije izvodis ...
za ojlerovu f-ju ni ne znam ... :D
ali ako ti kazes da moze tako da se uradi, neka ti je ...
e i ja bi volio da vidim tu Ojlerovu f-ju
Ojlerova funkcija, \phi (n) oznacava broj prirodnih brojeva manjih od n koji su uzajamno prosti sa n, a racuna se ovako:
n=p_1^{\alpha_1} p_2^{\alpha_2}\ldots p_k^{\alpha_k}
\phi (n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_k})
e sad kako ja to da primjenim na ovaj zadatak?
Pa napravis faktorizaciju broja n i primenis formulu. ;)
Javlja mi na 2 testa TLE, gdje je greška ???
http://z-trening.com/submit.php?submit=7100210689&subm_code=1
Iskoristi da je faktor <= sqrt(broj).
@halil
sad je normalan na vremenu ali prolazi 5/20
Pogledaj svoj poslednji post: http://www.z-trening.com/submit.php?submit=7100210818&subm_code=1
@ halil
Zahvaljujem na pomoći!!!
