Yes i have .. and i have the worst time in the rank page :) On Fri, Jan 29, 2010 at 8:51 PM, fundoonick <fundoon...@yahoo.co.in> wrote:
> I tried this problem using the method of solving using eulerphi values. > I calculate values of eulerphi in O(nlogn) and then use them to calculate > gcdsum using a similar algorithm in O(nlogn). > For n=10^6, O(nlogn) should work, but I am getting TLE on SPOJ. > Cant figure out why. > > Has anyone solved it using values of eulerphi? > > > On Fri, Jan 29, 2010 at 6:14 AM, ShingRay <masterrays...@gmail.com> wrote: > >> https://www.spoj.pl/problems/GCDEX/ >> >> #include <cstdio> >> using namespace std; >> >> const int N = 1000001; >> bool sifted[N] = {}; >> int primes[80000], nprimes = 0; >> long long gcdsum[N]; >> >> int main() >> { >> int n; >> gcdsum[0] = 0; >> gcdsum[1] = 1; >> for (int i = 2; i < N; ++i) >> { >> if (!sifted[i]) >> { >> primes[nprimes++] = i; >> gcdsum[i] = 2*i-1; >> } >> for (int j = 0; j < nprimes && i*primes[j] < N; ++j) >> { >> sifted[i*primes[j]] = true; >> if (i%primes[j] == 0) >> { >> int n = i*primes[j], m = 0, nn = 1; >> while (n%primes[j] == 0) >> n /= primes[j], ++m, nn *= >> primes[j]; >> gcdsum[i*primes[j]] = >> ((m+1)*nn-m*(nn/primes[j])) * gcdsum[n]; >> break; >> } >> gcdsum[i*primes[j]] = gcdsum[i]*gcdsum[primes[j]]; >> } >> } >> for (int i = 1; i < N; ++i) >> gcdsum[i] += gcdsum[i-1]-i; >> while (scanf("%d", &n), n) >> printf("%lld\n", gcdsum[n]); >> } >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > Please access the attached hyperlink for an important electronic > communications disclaimer: > http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php > > > > -- > > > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > > > To post to this group, send email to algoge...@googlegroups.com. > > > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > <algogeeks%2bunsubscr...@googlegroups.com>. > > > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
