My Weblog

Blog about programming and math

SPOJ LCM Sum

LCM Sum can be solved using this formula and pre computation of Euler totient function.

#include<cstdio>
#include<iostream>
#include<cmath>
#define Lim  1000000
using namespace std;
long long etf[1000010]  ;
long long  ret[1000010];

    void cal_etf()
       {
          for(int i = 1 ;i <= Lim ; i++ ) etf[i]=i;
          for(int i=2 ; i<= Lim ; i++ )
            if ( etf[i] == i)
              for(int j = 2*i ; j <= Lim ; j += i) etf[j] -=  etf[j]/ i ;
          for(int i=2 ; i<= Lim ; i++) if ( etf[i]==i) etf[i] = i-1;
	  for(int i=1;i <= Lim ; i++) for (int j = i ; j <= Lim ; j += i  ) ret[j]+= i*etf[i];
       }

    int main()
       {
          cal_etf();
          int n,t , i, sqt;
          long long sum;
          
          for(scanf("%d",&t ) ; t>0 ; t--)
          {
             scanf("%d",&n);
             sum = ( 1 + ret[n] ) * n / 2;
             printf("%lld\n",sum);
                
          }
       }

Now i am looking for memory manipulation in Haskell. Probably array will be good but till now i am not familiar .

Advertisements

May 20, 2011 - Posted by | Programming

3 Comments »

  1. Hey man, can you please explain the call_etf function !
    awaiting your post . .

    Comment by Prashant | June 24, 2011 | Reply

    • please explain…

      Comment by amit | October 24, 2012 | Reply

  2. hi i am from iiit hyderbad . can u please tell how the euler totient function has been calculated ????
    My hometown is morar, gwalior

    Comment by tarak | September 2, 2013 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: