Number Theory

SPOJ LASTDIG Solution


//LASTDIG
using namespace std;
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#define LLU long long unsigned int
int main()
{
int repeat[10][4]={
{0,0,0,0},
{1,1,1,1},
{2,4,8,6},
{3,9,7,1},
{4,6,4,6},
{5,5,5,5},
{6,6,6,6},
{7,9,3,1},
{8,4,2,6},
{9,1,9,1}};

int N;
cin>>N;
int A, B;
while(N--)
{
cin>>A>>B;
if(!B) cout<<"1\n";
else cout<<repeat[A%10][(B-1)%4]<<endl;
}
return 0;
}
0 CommentsLeave a comment

UVA 10323 Solution

/*
  Name: UVA10323
  Author: zoom
  Date: 23/04/11
*/
using namespace std;
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<limits>
#include<cmath>
#include<queue>
#include<map>
#define LLU long long unsigned int
#define LLD long long double
#define FOR(i,N) for(int i=0;i<(N);i++)
int main()
{
    long long n;
    vector<LLU> fib;
    fib.push_back(1);
    fib.push_back(1);
    for(int i = 2; i < 14; i++)
    {
        fib.push_back(fib[i-1] * i);
    }
    while(scanf(“%lld”, &n)!=EOF)
    {
        if(n < 0)
        {
            if( n / 2 * 2 == n)
                printf(“Underflow!\n”);
            else
                printf(“Overflow!\n”);
        }
        else if(n<8)
        {
            cout<<“Underflow!\n”;
        }
        else if(n>13)
        {
            cout<<“Overflow!\n”;
        }
        else
        {
            cout<<fib[n]<<endl;
        }
    }
}
0 CommentsLeave a comment

UVA 10394 Solution

/*
  Name: UVA 10394
  Author: zoom
  Date: 10/07/11
*/
using namespace std;
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<limits>
#include<cmath>
#include<queue>
#include<map>
#define LLU long long unsigned int
#define LLD long long double
#define FOR(i,N) for(int i=0;i<(N);i++)
#define N 20000000
bool mark[N];
vector<int> prime;
vector<int> twins;
void calc()
{
    memset (mark, true, sizeof (mark));
    mark [0] = mark [1] = false;
    for ( int i = 4; i < N; i += 2 )
        mark [i] = false;
    for ( int i = 3; i * i <= N; i++ )
    {
        if ( mark [i] )
        {
            for ( int j = i * i; j < N; j += 2 * i )
                mark [j] = false;
        }
    }

    prime.clear ();
    prime.push_back (2);

    for ( int i = 3; i < N; i += 2 )
    {
        if ( mark [i] )
            prime.push_back (i);
    }
}

int main()
{
    calc();
    for(size_t i=1,len=prime.size();i<len;i++)
    {
        if(prime[i]-prime[i-1]==2)
            twins.push_back(prime[i-1]);
    }
    int n;
    while(scanf(“%d”,&n)!=EOF)
    {
        n=twins[n-1];
        printf(“(%d, %d)\n”,n,n+2);
    }
}

0 CommentsLeave a comment

UVA 446 Solution

/*
  Name:  UVA446
  Author: zoom
  Date: 11/06/11
*/
using namespace std;
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<limits>
#include<map>
#define LLU long long unsigned int
#define LLD long long double
#define FOR(i,N) for(int i=0;i<(N);i++)
int get_val(string s)
{
    int val,ret=0,pow=1;
    for(int i=s.length()-1;i>=0;i–)
    {
        ret=ret+pow*(s[i]-‘0’);
        pow=pow*2;
    }
    return ret;
}
int ans(string s1,string s2,char C)
{
    int g1=get_val(s1),g2=get_val(s2);
    if(C==’+’) return g1+g2;
    else return g1-g2;
}
int main()
{
    map<char,string> mymap;
    mymap[‘0’]=”0000″;mymap[‘1’]=”0001″;mymap[‘2’]=”0010″;mymap[‘3’]=”0011″;
    mymap[‘4’]=”0100″;mymap[‘5’]=”0101″;mymap[‘6’]=”0110″;mymap[‘7’]=”0111″;
    mymap[‘8’]=”1000″;mymap[‘9’]=”1001″;mymap[‘A’]=”1010″;mymap[‘B’]=”1011″;
    mymap[‘C’]=”1100″;mymap[‘D’]=”1101″;mymap[‘E’]=”1110″;mymap[‘F’]=”1111″;
    int cases;
    string A,B,s1,s2;
    char C;
    cin>>cases;
    while(cases–)
    {
        cin>>A>>C>>B;
        s1=””,s2=””;
        FOR(i,A.length())
        s1=s1+mymap[A[i]];
        FOR(i,B.length())
        s2=s2+mymap[B[i]];
        while(s1.length()!=13)
        s1=”0″+s1;
        while(s2.length()!=13)
        s2=”0″+s2;
        cout<<s1<<” “<<C<<” “<<s2<<” = “<<ans(s1,s2,C)<<endl;
    }
}

0 CommentsLeave a comment

UVA 324 solution

/*
  Name:  UVA324
  Author: zoom
  Date: 11/06/11
*/
using namespace std;
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<limits>
#include<map>
#define LLU long long unsigned int
#define LLD long long double
#define FOR(i,N) for(int i=0;i<(N);i++)
vector<string> fct;
string calc(int mul)
{
    string s=fct.back(),ret=””;
    int val=0,carry=0;
    for(int i=0;i<s.length();i++)
    {
        val=(s[i]-‘0’)*mul+val;
        ret.push_back(val%10+’0′);
        val=val/10;
    }
    while(val!=0)
    {
        ret.push_back(val%10+’0′);
        val/=10;
    }
    return ret;
}
int main()
{
    fct.push_back(“1”);
    fct.push_back(“1”);
    for(int i=2;i<367;i++)
    {
        fct.push_back(calc(i));
    }
    int N,S;
    while(cin>>N)
    {
        if(!N) break;
        printf(“%d! –\n”,N);
        S=fct[N].length();
        for(int i=0;i<10;i++)
        {
            printf(”   (%d)%5d”,i,(int)count(fct[N].begin(),fct[N].end(),’0’+i));
            if(i==4) printf(“\n”);
        }
        printf(“\n”);
    }
}

0 CommentsLeave a comment