Tags » Sieve

Light OJ 1028 - Trailing Zeroes (I) [solved]

/******************************************
          Mobarak Hosen Shakil
        ICE, Islamic University
     ID: mhiceiuk(all), 29698(LOJ)
   E-mail: mhiceiuk @ (Gmail/Yahoo/FB)
 Blog: https://iuconvergent.wordpress.com
*******************************************/

#include<bits/stdc++.h>
#define sroot 1000007

using namespace std;
vector <int> primes;


int sieve()
{
    bool a;
    memset(a, 0, sizeof(a));

    for(int i = 2; i <= sroot; i++) {
        if(a[i] == 0) {
            for (int j = i + i; j <= sroot; j = j + i) {
                a[j] = 1;
            }

        }

    }
    primes.push_back(2);
    for (int i = 3; i <= sroot; i+=2) {
        if(a[i] == 0) {
            primes.push_back(i);
        }

    }

}

int main()
{
    sieve();

    int t;
    long long x, sum, k, temp, n;
    ///cout<<primes.size()<<endl;

    scanf("%d", &t);

    for (int cases = 1; cases <= t; cases++) {
        scanf("%lld", &x);
        sum = 1;
        n = sqrt(x);

        for(int i = 0; i <= primes.size() - 1 and primes[i] <= n ; i++) {

            k = 0;
            if(x < primes[i]) {
                break;
            }

            while(x % primes[i] == 0) {

                x = x / primes[i];
                k++;
            }

            sum = sum * (k + 1);

        }

        if(x > 1) sum *= 2;
        ///cout << x << endl;
        sum = sum - 1;

        printf("Case %d: %lld\n",cases, sum);

    }

}
Light OJ

UVa 10791 - Minimum Sum LCM [solved]

/******************************************
          Mobarak Hosen Shakil
        ICE, Islamic University
     ID: mhiceiuk(all), 29698(LOJ)
   E-mail: mhiceiuk @ (Gmail/Yahoo/FB)
 Blog: https://iuconvergent.wordpress.com
*******************************************/

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define M 100000000
int marked;
#define on(x) (marked & (1<<((x%64)/2)))
#define mark(x) marked |= (1<<((x%64)/2))

typedef long long LL;

vector<int> p;

bool isPrime(int num) {
    return num > 1 && (num == 2 || ((num & 1) && !on(num)));
}

void sieve(int n)
{
    p.pb(2);
    for (int i = 3; i * i < n; i += 2) {
        if (!on(i)) {
            p.pb(i);
            for (int j = i * i; j <= n; j += i + i) {
                mark(j);
            }
        }
    }

    for(int i=3; i<n; i+=2)
        if(isPrime(i))p.pb(i);
}


int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n, cn=0;
    sieve(46350);
    while(cin>>n && n!=0)
    {

        LL pr, sum=0;
       //// cout<<p.size()<<endl;
        int fact=0;
        if(n==1){
            sum=2;
        }
        else
        {
            for(int i=0; i<p.size() && n!=1; i++)
            {
                if(n%p[i]==0)
                {
                    pr=1;
                    while(n%p[i]==0 && n!=1)
                    {
                        n/=p[i];
                        pr*=p[i];
                    }
                    sum+=pr;
                    fact++;
                }
            }
            if(n>1) {
                fact++;
                sum+=n;
            }
            if(fact<2)sum+=1;
        }
        cout<<"Case "<<++cn<<": "<<sum<<endl;
    }
    return 0;
}
UVa Problems

Sunday

Garlic

The second thing that Loved One said to me this morning was “you still smell of garlic”. I was starting to get a little paranoid about the smell of garlic. 323 more words

Random Thoughts

Enter: the Censor


Listen to yourself breathe.
Look outward with glossy stare.
Become the hunted.
Become what you seek.
Then never look into the mirror.

Press eyes into the sieve. 26 more words

Poetry

Sieve

Do not pour your time and emotion into
Petty disagreements

For these are merely

False vessels;

Sieves

Which drain the

Giver

And create nothing but

Illusions.

Light OJ 1109 - False Ordering

/******************************************
          Mobarak Hosen Shakil
        ICE, Islamic University
     ID: mhiceiuk(all), 29698(LOJ)
   E-mail: mhiceiuk @ (Gmail/Yahoo/FB)
 Blog: http://iuconvergent.wordpress.com
*******************************************/

#include<bits/stdc++.h>
using namespace std;

#define mh                    main
#define IOS                   ios_base::sync_with_stdio(0);cin.tie(0)

#define F(i, a, b)            for(int i=a; i<b; i++)
#define B(i, b, a)            for(int i=b; i>=a; i--)

#define D                     double
#define LL                    long long int
#define ULL                   unsigned LL

#define Max(a,b)              ((a>b)?a:b)
#define Min(a,b)              ((a>b)?b:a)
#define _Max(a, b, c)         Max(a, Max(b, c))
#define _Min(a, b, c)         Min(a, Min(b, c))

#define all(a)                a.begin(), a.end()
#define srt(a, n)             sort(a, a+n)

#define chr                   getchar()
#define PI                    acos(-1)
#define sq(n)                 (n*n)
#define Bitcnt(a)             __builtin_popcountll(a)
#define mem(x, val)           memset(x, val, sizeof(x))
#define pb                    push_back
#define mp                    make_pair
#define sc                    scanf
#define pf                    printf
#define sz                    size
#define ft                    front
#define ps                    push
#define ff                    first
#define ss                    second
#define em                    empty

template<typename T>inline T Gcd(T a,T b){if(a<0)return Gcd(-a,b);if(b<0)return Gcd(a,-b);return (b==0)?a:Gcd(b,a%b);}
template<typename T>inline T Lcm(T a,T b) {if(a<0)return Lcm(-a,b);if(b<0)return Lcm(a,-b);return a*(b/Gcd(a,b));}
template<typename T>inline T POW(T B,T P){ if(P==0) return 1; if(P&1) return B*POW(B,P-1);  else return sq(POW(B,P/2));}
template<typename T>inline T Bigmod(T base, T power, T MOD){T ret=1;while(power){if(power & 1)ret=(ret*base)%MOD;base=(base*base)%MOD;power>>=1;}return ret;}
template<typename T>inline T ModInverse(T number, T MOD){return Bigmod(number, MOD-2, MOD);}

bool isVowel(char ch){ ch=toupper(ch); if(ch=='A'|ch=='U'||ch=='I'||ch=='O'||ch=='E') return true; return false;}
bool isConst(char ch){if (isalpha(ch) && !isVowel(ch)) return true; return false;}
///****************************************************************************///

typedef pair<int, int> pii;
typedef vector< pii > vii;
typedef vector<int> vi;

const int INF = (1<<30);

vi prime;
int res;
int pos;
void prime_generate()
{
    bitset<1001>mask;

    prime.pb(2);
    for(int i=4; i<1001; i+=2) mask[i]=1;
    for(int i=3; i<1001; i+=2)
    {
        if(mask[i]==0)
        {
            prime.pb(i);
            for(int j=(2*i); j<1001; j+=i)
            {
                mask[j]=1;
            }
        }
    }
}

void number_of_divisors()
{
    prime_generate();
    F(i, 2, 1001)
    {
        int cnt=1, num=i;
        for(int j=0; prime[j]<=i && j<prime.sz(); j++)
        {
            int dd=0;
            while(!(num%prime[j]))
            {
                num/=prime[j];
                dd++;
            }
            cnt*=(dd+1);
        }
        res[i]=cnt;
    }
}

void False_Ordering()
{
    pos[1]=1;
    int l=1;
    F(i, 2, 33)
    {
        B(j, 1000, 2)
        {
            if(res[j]==i)
            {
                pos[++l]=j;
            }
        }
    }
}

int mh()
{
///    IOS;
    int tn;
    sc("%d", &tn);
    number_of_divisors();
    False_Ordering();
    F(i, 1, tn+1)
    {
        int nth;
        sc("%d", &nth);
        pf("Case %d: %d\n", i, pos);
    }
    return 0;
}

Light OJ