LightOj 1007 - Mathematically Hard

By -

Solving Tips :: Euler's totient function

 // Verdict : Accepted
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <cctype>
#include <sstream>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#define sf scanf
#define pf printf
#define sfint scanf ("%d %d",&a,&b)
#define sfl scanf ("%ld %ld",&a,&b)
#define sfll scanf ("%lld %lld",&a,&b)
#define sfd scanf ("%lf %lf",&a,&b)
#define sff scanf ("%f %f",&a,&b)
#define lp1(i,n) for(i=0;i<n;i++)
#define lp2(i,n) for(i=1;i<=n;i++)
#define LL long long
#define L long
#define mem(c,v) memset(c,v,sizeof(c))
#define ui unsigned int
#define ull unsigned long long int
#define nl puts("")
#define MX 5000009
#define N 100
#define MOD 10000000007
#define pb push_back
#define pi acos(-1.0)
#define sz size()
#define gc getchar ()
#define ps push
#define clr clear
#define bn begin()
#define ed end()

using namespace std;

int prime[MX+5]; // generating bit wise seieve 

int setbit(int n, int pos)
{
    n = n|(1<<pos);
    return n;
}

bool checkbit(int n, int pos)
{
    n=n&(1<<pos);
    return n;
}

void seieve(int n)
{
    int i,j,x=sqrt(n);

    prime[0]=setbit(prime[0],0);
    prime[0]=setbit(prime[0],1);

    for(i=4;i<=n;i+=2)
    {
        prime[i>>5] = setbit(prime[i>>5],i&31);
    }

    for(i=3;i<=x;i+=2)
    {
        if(!checkbit(prime[i>>5],i&31))
        {
            for(j=i+i;j<=n;j+=i)
            {
                prime[j>>5] = setbit(prime[j>>5],j&31);
            }
        }
    }
}

ull phi[MX+5];

void euler_phi()
{
    ull i,k,p;

    for(i=1;i<=MX;i++) phi[i]=i;

    for(p=2;p<=MX;p++)
    {
        if(!checkbit(prime[p>>5],p&31))
        {
            if(phi[p]==p)
            {
                for(k=p;k<=MX;k+=p)
                {
                    phi[k]-=phi[k]/p;
                }
            }
        }
    }
}

int main()
{
    seieve(MX);
    euler_phi();
    ull i;
    for(i=2;i<=MX;i++)
    {
        phi[i]=phi[i-1]+(phi[i]*phi[i]);
    }

    ull t,tc,x,y;
    sf("%llu",&tc);
    for(t=1;t<=tc;t++)
    {
        sf("%llu %llu",&x,&y);
        pf("Case %llu: %llu\n",t,phi[y]-phi[x-1]);
    }

    return 0;
}
Version :: 02 
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <cctype>
#include <sstream>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#define sf scanf
#define pf printf
#define sfint scanf ("%d %d",&a,&b)
#define sfl scanf ("%ld %ld",&a,&b)
#define sfll scanf ("%lld %lld",&a,&b)
#define sfd scanf ("%lf %lf",&a,&b)
#define sff scanf ("%f %f",&a,&b)
#define lp1(i,n) for(i=0;i<n;i++)
#define lp2(i,n) for(i=1;i<=n;i++)
#define LL long long
#define L long
#define mem(c,v) memset(c,v,sizeof(c))
#define ui unsigned int
#define ull unsigned long long int
#define nl puts("")
#define MX 5000009
#define N 100
#define MOD 10000000007
#define pb push_back
#define pi acos(-1.0)
#define sz size()
#define gc getchar ()
#define ps push
#define clr clear
#define bn begin()
#define ed end()

using namespace std;

bool stats[MX];

void seieve()
{
    mem(stats,false);
    ull i,j,qrt;

    stats[0]=stats[1]=true;

    for(i=4;i<=MX;i+=2) stats[i]=true;

    qrt = (unsigned long) sqrt(double(MX));

    for(i=3;i<=qrt;i+=2)
    {
        if(!stats[i])
        {
            for(j=i*i;j<=MX;j+=i+i)
            {
                stats[j]=true;
            }
        }
    }
}

ull phi[MX];

void euler_phi()
{
    ull i,k,p;

    for(i=1;i<MX;i++) phi[i]=i;

    for(p=2;p<MX;p++)
    {
        if(!stats[p])
        {
            if(phi[p] == p)
            {
                for(k=p;k<MX;k+=p)
                {
                    phi[k]-=phi[k]/p;
                }
            }
        }
    }
}

int main()
{
    seieve();
    euler_phi();

    ull i,j,t,tc;

    for(i=2;i<MX;i++)
    {
        phi[i] = (phi[i]*phi[i]);
        phi[i]+=phi[i-1];
    }

    sf("%llu",&tc);

    for(t=1;t<=tc;t++)
    {
        ull x,y;

        sf("%llu %llu",&x,&y);

        pf("Case %llu: %llu\n",t,phi[y]-phi[x-1]);
    }

    return 0;
}

Comments

Post a Comment

Popular posts from this blog

LeetCode Palindrome Number

By -
 Problem Description Link:  https://leetcode.com/problems/palindrome-number/ Accepted Solution /* The solution is easy, and I believe everyone knows the process. However, one problem is that x is a number. If it is a string, in that case, we can get the result after reversing it. Therefore, to solve the problem, we have to find the digits by modulating 10, store them in an array, and finally compare from both sides. If we find any discrepancy, we can tell it is not a palindrome. Note that any negative integer would never be a palindrome since it should contain a minus (-) sign. */ class Solution { public:     bool isPalindrome ( int x ) {         int digit [ 50 ], len= 0 ;         bool f = true ;         if (x < 0 ) {             return false ;         }         while (x> 0 )         {       ...
Read more

Hacker Rank The Power Sum

By -
Problem Link: The Power Sum #include<bits/stdc++.h> using namespace std; #define fast ios_base::sync_with_stdio(0) #define bfast cin.tie(0) #define outs(x) cout << x << " " #define outn(x) cout << x << "\n" #define sf scanf #define pf printf #define pfn(x , k) printf(k , x) #define nl puts("") #define psb push_back #define mset(c,v) memset(c , v , sizeof c) #define loop0(n) for(int i=0; i<n; i++) #define loop1(n) for(int i=1; i<=n; i++) #define mpair(x , y) make_pair(x , y) #define all(x) x.begin(), x.end() #define pi acos(-1.0) #define psb push_back #define clr clear() typedef unsigned long long ull; typedef long long LL; typedef vector<int>vii; typedef vector<LL>vll; typedef vector<string>vs; typedef map<int, int>mpii; typedef map<string, int>mpsi; typedef map<char, int>mpci; typedef map<LL, LL>mpll; const int mod = 1000007; const int high = 1002; int x = 0 , y; int getWay(L...
Read more

SPOJ-CMG - Collecting Mango

By -
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<queue> #include<stack> #include<map> #include<cmath> #include<algorithm> #define psb push_back #define ppb pop_back #define all(x) x.begin(),x.end() #define N 1000100 #define sf scanf #define pf printf using namespace std; typedef long long LL; typedef vector<LL>vll; LL ar[N] , num[N]; int main() {     int t , tc=0;     //cin >> t;     sf("%d",&t);     while(t--)     {         LL n, x, arlen=-1, nmlen=-1 , i , maxi=-1 , zar;         char c;         //cin >> n;         sf("%lld",&n);         //cout << "Case " << ++tc << ":\n";       ...
Read more