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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
