Skip to main content

Posts

Showing posts with the label SPOJ

SPOJ --- BUGLIFE - A Bug’s Life

Bismillahir Rahmanir Rahim Just  bicolour  it. ///Author: Tanvir Ahmmad ///CSE,Islamic University,Bangladesh #include< iostream > #include< cstdio > #include< algorithm > #include< string > #include< cstring > #include< sstream > #include< cmath > #include< cstring > #include< vector > #include< queue > #include< map > #include< set > #include< stack > #include< vector > #include< iterator > #include   < functional >   ///sort(arr,arr+n,greater<int>()) for decrement of array /*every external angle sum=360 degree   angle find using polygon hand(n) ((n-2)*180)/n*/ ///Floor[Log(b)  N] + 1 = the number of digits when any number is represented in base b using   namespace  std; typ...

SPOJ --- AMR10C - Square Free Factorization

Bismillahir Rahmanir Rahim ///Author: Tanvir Ahmmad ///CSE,Islamic University,Bangladesh #include< iostream > #include< cstdio > #include< algorithm > #include< string > #include< cstring > #include< sstream > #include< cmath > #include< cstring > #include< vector > #include< queue > #include< map > #include< set > #include< stack > #include< vector > #include< iterator > #include   < functional >   ///sort(arr,arr+n,greater<int>()) for decrement of array /*every external angle sum=360 degree   angle find using polygon hand(n) ((n-2)*180)/n*/ ///Floor[Log(b)  N] + 1 = the number of digits when any number is represented in base b using   namespace  std; typedef   long   long ...

SPOJ --- AMR11E - Distinct Primes

Bismillahir Rahmanir Rahim ///Author: Tanvir Ahmmad ///CSE,Islamic University,Bangladesh #include< iostream > #include< cstdio > #include< algorithm > #include< string > #include< cstring > #include< sstream > #include< cmath > #include< cstring > #include< vector > #include< queue > #include< map > #include< set > #include< stack > #include< vector > #include< iterator > #include   < functional >   ///sort(arr,arr+n,greater<int>()) for decrement of array /*every external angle sum=360 degree   angle find using polygon hand(n) ((n-2)*180)/n*/ ///Floor[Log(b)  N] + 1 = the number of digits when any number is represented in base b using   namespace  std; typedef   long   long ...

SPOJ --- GCDEX - GCD Extreme

I just solve this problem after well understanding of euler totient function. First of all we solve simple problem  ∑ n i = 1 g c d ( i , n ) ∑ i = 1 n g c d ( i , n ) . How can you solve this. We can write this function as  ∑ g ∗ c n t [ g ] ∑ g ∗ c n t [ g ] where g is gcd of pair(i,n). and cnt[g] =total number of pair having gcd g. And we simply need summation of this. Thanks to following gcd identity As we know gcd(a,b)=g, then gcd(a/g,b/g)=1 then our equation simply becomes  ∑ d | n d ∗ p h i [ n / d ] ∑ d | n d ∗ p h i [ n / d ] where phi[] is euler totient number.(only divisors because gcd of pair(i,n) can only be divisors of n). After that it is simple iterator over divisors of n and sum all value d*phi[n/d]. Now came to original question now we need all pair(i,j) in summation place. That is for each value of i from 1 to n  ∑ n i = 1 g c d ( i , n ) ∑ i = 1 n g c d ( i , n ) . But we have to preprocess all values of phi[i] , d*phi[n/d] and some other. Example...

SPOJ --- LCMSUM - LCM Sum

∑LCM(i, n) = ((∑(d * ETF(d)) +  1 ) * n) /  2   where  ETF(d) is Euler totient function of d and d belongs to the set of divisors of n. Example:  Let n be  5  then LCM( 1 ,  5 ) + LCM( 2 ,  5 ) + LCM( 3 ,  5 ) + LCM( 4 ,  5 ) + LCM( 5 ,  5 )  =  5  +  10  +  15  +  20  +  5   =  55 With Euler Totient Function:  All divisors of  5  are { 1 ,  5 }  Hence, (( 1 *ETF( 1 ) +  5 *ETF( 5 ) +  1 ) *  5 ) /  2  =  55   Bismillahir Rahmanir Rahim ///Author: Tanvir Ahmmad ///CSE,Islamic University,Bangladesh #include< iostream > #include< cstdio > #inclu...