UVa 1152 – 4 Values whose Sum is 0


/*
User ID: turing_13
Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3593
*/

#include <bits/stdc++.h>

#define pii pair <int,int>
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define oo 1<<29
#define dd double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define MAX 100
#define SZ(a) (int)a.size()
#define getint(a) scanf("%d",&a)
#define loop(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define inf 1000000
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define I int


using namespace std;

ll ara[4010][4];
vector<ll>ab;

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int n,t;
    sc("%d",&t);
    while(t--)
    {
        ll ans=0;
        sc("%d",&n);
        for(int i=0; i<n; i++)
        {
            sc("%lld %lld %lld %lld",&ara[i][0],&ara[i][1],&ara[i][2],&ara[i][3]);
        }
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
            {
                ab.pb(ara[i][0]+ara[j][1]);
            }
        sort(all(ab));
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
            {
                int val= -(ara[i][2]+ara[j][3]);
                ans+= upper_bound(all(ab),val)-lower_bound(all(ab),val);
            }
        pf("%lld\n",ans);
        if(t)
            pf("\n");
    ab.clear();
    }
    return 0;
}

Advertisements

UVa 438 – The Circumference of the Circle

Problem Link : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=379


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

double dist(double x1, double y1, double x2, double y2)
{
    return sqrt(sqr(x1-x2)+sqr(y1-y2));
}

int main()
{

    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);


    double x1,y1,x2,y2,x3,y3;
    while(cin>>x1>>y1>>x2>>y2>>x3>>y3)
    {
        double a,b,c;

        //calculating the three side of the triangle

        a=dist(x1,y1,x2,y2);
        b=dist(x2,y2,x3,y3);
        c=dist(x1,y1,x3,y3);

        // calculating the sub perimeter

        double s=(a+b+c)/2.0;

        // calculating the area of the triangle.

        double area=sqrt(s*(s-a)*(s-b)*(s-c));

        // calculating radius using formula area= (a*b*c)/(2*R) ; here R = diameter

        double r=(a*b*c)/(4.0*area);

        cout<<setprecision(2)<<fixed<<Pi*2.0*r<<endl;

    }

    return 0;
}


UVa : 10938 – Flea circus

Problem Link : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1879

Solution Idea: Find the LCA. Then find the middle node and middle+1 node on the path connection two nodes which are given in the query. Here I use an extra DFS to find the path on a reverse graph g2.


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

#define mx 5005
int n,q;

vector<int>g1[mx],g2[mx];

int sparse_par[mx][14],sparse_dis[mx][14];

int level[mx],par[mx];

void dfs(int u, int cnt, int from)
{
    par[u]=from;
    level[u]=cnt;
    g2[u].pb(from);

    for(int i=0;i<SZ(g1[u]);i++)
    {
        int v=g1[u][i];
        if(v!=from)
        {
            dfs(v,cnt+1,u);
        }
    }
}


void build_talbe()
{
    for(int i=1;i<=n;i++)
    {
        sparse_par[i][0]=par[i];
        sparse_dis[i][0]=1;
    }
    sparse_dis[1][0]=0;

    for(int j=1; 1<<j<=n;j++)
    {
        for(int i=1;i<=n;i++)
        {
            sparse_par[i][j]=sparse_par[sparse_par[i][j-1]][j-1];
            sparse_dis[i][j]=sparse_dis[i][j-1]+sparse_dis[sparse_par[i][j-1]][j-1];
        }
    }
}

int LCA;

int query(int p, int q)
{
    if(level[p]<=level[q]) swap(p,q);

    int log=log2(level[p]);

    int ret=0;

    for(int i=log;i>=0;i--)
    {
        if(level[p]-(1<<i)>=level[q])
        {
            ret+=sparse_dis[p][i];
            p=sparse_par[p][i];
        }
    }


    if(p==q){LCA=p; return ret;}

    for(int i=log;i>=0;i--)
    {
        if(sparse_par[p][i]!=sparse_par[q][i])
        {
            ret+=sparse_dis[p][i];
            ret+=sparse_dis[q][i];
            p=sparse_par[p][i];
            q=sparse_par[q][i];
        }
    }
    ret+=2;
    LCA=par[p];
    return ret;
}


vector<int>temp;

int dfs1(int u, int cnt)
{
    if(u==LCA) return u;
    temp.pb(u);
    if(cnt==0) return u;
    for(int i=0;i<SZ(g2[u]);i++)
        return dfs1(g2[u][i],cnt-1);
}

int main()
{

//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);

    while(sf(n) && n)
    {
        loop(i,n-1)
        {
            int a,b;
            sff(a,b);
            g1[a].pb(b);
            g1[b].pb(a);
        }

        dfs(1,0,1);

        build_talbe();

        sf(q);

        while(q--)
        {
            int a,b;
            sff(a,b);

            int dis=query(a,b)+1;

            if(dis%2==0)
            {
                temp.clear();
                dfs1(a,n);
                temp.pb(LCA);
                int x=SZ(temp);
                dfs1(b,n);
                reverse(temp.begin()+x,temp.end());
                int aa=temp[(dis/2)-1];
                int bb=temp[dis/2];
                pf("The fleas jump forever between %d and %d.\n",min(aa,bb),max(aa,bb));

            }
            else
            {
                int p;
                if(level[a]>level[b])
                    p=a;
                else
                    p=b;
                pf("The fleas meet at %d.\n",dfs1(p,dis/2));
            }
        }

        for(int i=0;i<=n;i++)
        {
            g1[i].clear();
            g2[i].clear();
        }

    }


    return 0;
}


UVa : 12238 – Ants Colony

Problem Link : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3390


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

#define mx 100005

int n;
int level[mx],par[mx],dis[mx];

vector<int>g[mx],cost[mx];

ll sparse_par[mx][20],sparse_sum[mx][20];

void dfs(int u, int cnt, int from)
{
    par[u]=from;
    level[u]=cnt;

    for(int i=0;i<SZ(g[u]);i++)
    {
        int v=g[u][i];

        if(v!=from)
        {
            dis[v]=cost[u][i];
            dfs(v,cnt+1,u);
        }

    }

}


void build_table()
{
    for(int i=0;i<n;i++)
    {
        sparse_par[i][0]=par[i];
        sparse_sum[i][0]=dis[i];
    }

    for(int j=1;1<<j<n;j++)
    {
        for(int i=0;i<n;i++)
        {
            sparse_par[i][j]=sparse_par[sparse_par[i][j-1]][j-1];
            sparse_sum[i][j]=sparse_sum[i][j-1]+sparse_sum[sparse_par[i][j-1]][j-1];
//            D(i);
//            D(j);
//            D(sparse_par[i][j]);
//            D(sparse_sum[i][j]);
        }
    }

}


ll query(int p, int q)
{
    ll ret=0;
    if(level[p]<=level[q]) swap(p,q);

    int log=log2(level[p]);

    for(int i=log;i>=0;i--)
    {
        if(level[p]-(1<<i)>=level[q])
        {
            ret+=sparse_sum[p][i];
            p=sparse_par[p][i];
        }
    }

    if(p==q) return ret;

    for(int i=log;i>=0;i--)
    {
        if(sparse_par[p][i]!=sparse_par[q][i])
        {
            ret+=sparse_sum[p][i];
            ret+=sparse_sum[q][i];
            p=sparse_par[p][i];
            q=sparse_par[q][i];
        }
    }


    ret+=dis[p];
    ret+=dis[q];
    return ret;

}

int main()
{

//    freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    while(sf(n) && n)
    {
        for(int i=1;i<n;i++)
        {
            int a,b;
            sff(a,b);
            g[i].pb(a);
            g[a].pb(i);
            cost[a].pb(b);
            cost[i].pb(b);
        }

        dis[0]=0;

        dfs(0,0,0);

        build_table();

        int q;
        sf(q);

        bool test=1;

        while(q--)
        {
            int a,b;
            sff(a,b);

            ll ans=query(a,b);

            if(test)
            {
                printf("%lld",ans);
                test=0;
            }
            else
            {
                printf(" %lld",ans);
            }

        }

        printf("\n");

        for(int i=0;i<=n;i++)
        {
            g[i].clear();
            cost[i].clear();
        }

    }

    return 0;
}

UVa 10278 – Fire Station

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1219

Solution Idea:

In this problem the most challenging part is determine how the input is given.
Here for each test case number of edge in the graph is not fixed. You need to take input till end of file. For this strignstream class is used.

And the algorithmic idea is similar like complete search. Place an additional fire station on every intersection which do not contain any fire station already. and run dijkstra for this graph. every time you place a new fire station on an intersection you have to run a dijkstra taking that node as source and also the existing fire stations by input as source. just print the minimum intersection number which minimize the maximum distance.


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

struct data
{
    int u,cost;
    data(int a,int b)
    {
        u=a,cost=b;
    }
    bool operator < (const data &p) const
    {
        return cost>p.cost;
    }
};


vector<int>graph[600],cost[600];
ll dis[600];
bool vis[600];
set<int>st;
int f,k;

void all_clear(int n)
{
    for(int i=0;i<=550;i++)
    {
        graph[i].clear();
        cost[i].clear();
        dis[i]=(1<<28);
        vis[i]=0;
    }
    st.clear();
}


ll dijkastra(int src)
{
    for(int i=0;i<600;i++) dis[i]=(1<<28);

    priority_queue<data>Q;

    stlloop(st)
    {
        dis[*it]=0;
        Q.push(data(*it,0));
    }
    Q.push(data(src,0));
    dis[src]=0;
    ll ret=0;

    while(!Q.empty())
        {
            data u=Q.top();
            Q.pop();
            for(int i=0;i<SZ(graph[u.u]);i++)
            {
                int v=graph[u.u][i];
                if(u.cost+cost[u.u][i]<dis[v])
                {
                    dis[v]=u.cost+cost[u.u][i];
                    Q.push(data(v,dis[v]));
                }

            }
        }

        for(int i=1;i<=k;i++)
            ret=max(ret,dis[i]);
        return ret;
}


int main()
{

//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
//    CIN;
    int t;
    cin>>t;
    TEST_CASE(t)
    {
//        vector<int>source;
        cin>>f>>k;

        all_clear(k);
        st.clear();

        for(int i=0;i<f;i++)
        {
            int a;
            cin>>a;
            dis[a]=0;
            st.insert(a);
            vis[a]=1;
        }

            string str;
            getline(cin,str);

        while(1)
        {
            getline(cin,str);
            stringstream ss(str);
            if(str.empty()) break;
            int a,b,c;
            ss>>a>>b>>c;
            graph[a].pb(b);
            graph[b].pb(a);
            cost[a].pb(c);
            cost[b].pb(c);
        }



        int ans=1,maxi=100000000;
        for(int i=1;i<=k;i++)
        {
            if(vis[i]==0)
            {
                ll temp=dijkastra(i);
                if(temp<maxi)
                {
                    maxi=temp;
                    ans=i;
                }
            }
        }

        cout<<ans<<endl;
        if(z!=t)
            cout<<endl;
    }

    return 0;
}


UVa 455 – Periodic Strings

Problem Link : https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=396

solutin idea: straight forward from Shanto vhai’s book. formula : n-phi(n-1)-1 .


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

int compute_prefix(int n, string str)
{
    vector<int>phi(n);
    int k=0;
    for(int i=1;i<n;i++)
    {
        while(k>0 && str[i]!=str[k]) k=phi[k-1];
        if(str[i]==str[k]) k++;
        phi[i]=k;
    }
    return phi[n-1]-1;
}

int main()
{

    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    CIN;
    int t;
    cin>>t;
    TEST_CASE(t)
    {
        string str;
        cin>>str;
        int aa=SZ(str);
        int n=compute_prefix(aa,str);
        int ans=aa-n-1;
        if(aa%ans==0)
            cout<<ans<<endl;
        else
            cout<<aa<<endl;
        if(z<t)
            cout<<endl;
    }


    return 0;
}

UVa 10139 – Factovisors

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1080

Solution Idea:

Calculate the prime factor of M. Let a prime is P and it’s power is x. so P^x is a prime factor of M. then check that in N! prime factor of P is grater or equal to x.



#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

#define mx 100000

bitset<mx/2> vis;

vector<int>prime;

void sive()
{
    int x=mx/2,y=sqrt(mx)/2;

    for(int i=1; i<y; i++)
    {
        if(vis[i]==0)
        {
            for(int j=i*(i+1)*2; j<x; j+=(2*i)+1)
                vis[j]=1;
        }
    }

    prime.pb(2);
    for(int i=3; i<mx; i+=2)
        if(vis[i/2]==0)
            prime.pb(i);

}

int main()
{
    CIN;
//    freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    sive();

    ll n,m;
    while(cin>>n>>m)
    {
        ll a,b;
        a=n,b=m;
        ll root=sqrt(m)+1;
        bool test=0;
//        if(m==0) test=1;
        for(int i=0;prime[i]<root;i++)
        {
            if(m%prime[i]==0)
            {
                int cnt=0;
                while(m%prime[i]==0)
                    cnt++,m/=prime[i];
                ll temp=n;
                ll sum=0;
                while(temp)
                {
                    sum+=temp/prime[i];
                    temp/=prime[i];
                }
                if(sum<cnt)
                {
                    test=1;
                    break;
                }
                root=sqrt(m)+1;
            }
        }
        if(m>1)
        {
           ll temp=n;
                ll sum=0;
                while(temp)
                {
                    sum+=temp/m;
                    temp/=m;
                }
                if(sum<1)
                {
                    test=1;
                }
        }

        if(test==0)
            cout<<b<<" divides "<<a<<"!"<<endl;
        else
            cout<<b<<" does not divide "<<a<<"!"<<endl;
    }


    return 0;
}