[UVA] 516 - Prime Land

/*20141122 hanting*/
#include <iostream>
#include <sstream>
#include <cmath>
using namespace std;
int main()
{
    string s;
    while(getline(cin,s) && s!="0")
    {
        stringstream sin(s);
        int sum=1;
        int _pow;
        int num;
        while(sin>>num>>_pow) sum*=pow(num,_pow);
        sum--;
        bool Num[50000]={0};
        int prime[10000];
        int x=0;
        for(int i=2;i<50000;i++)
        {
            if(Num[i]==0)
            {
                prime[x++]=i;
                for(int j=i*2;j<50000;j+=i)
                {
                    Num[j]=1;
                }
            }
        }
        int ans[1000];
        int q=0;
        for(int i=0;sum!=1;i++)
        {
            while(sum%prime[i]==0)
            {
                ans[q++]=prime[i];
                sum/=prime[i];
            }
        }
        for(int i=q-1;i>=0;i--)
        {
            int pow=1;
            if(i!=q-1) cout<<" ";
            cout<<ans[i];
            while(i-1>=0 && ans[i-1]==ans[i])
            {
                pow++;
                i--;
            }
            cout<<" "<<pow;
        }
        cout<<endl;
    }
}

[UVA] 11879 - Multiple of 17

/*20141111 hanting*/
#include <iostream>
using namespace std;
int seventeen[105]={0};
inline bool compare(int *seventeen,int *num)
{
    for(int i=104;i>=0;i--)
    {
        if(num[i]>seventeen[i]) return 0;
        else if(num[i]<seventeen[i]) return 1;
    }
    return 1;
}
bool IsSeventeen(int* num,int p)
{
    if(compare(seventeen,num))
    {
        if((num[0]==7 && num[1]==1)||p==0) return 1;
        else return 0;
    }
    else
    {
        int d=num[0];
        d*=5;
        for(int i=0;i<p-1;i++)//shift ( remove the last number )
        {
            num[i]=num[i+1];
        }

        num[p-1]=0;
        p--;
        int sub_5d[105]={d};
        for(int i=1;i<2;i++)//carry
        {
            sub_5d[i]+=sub_5d[i-1]/10;
            sub_5d[i-1]%=10;
        }
        /*num-5d*/
        int siz=max(p,2);
        for(int i=0;i<siz;i++)
        {
            num[i]-=sub_5d[i];
        }
        for(int i=0;i<siz;i++)
        {
            if(num[i]<0)
            {
                num[i]+=10;
                num[i+1]--;
            }
        }
        if(num[siz]<0)//if( num < 5d )
        {
            num[siz]=0;
            for(int i=0;i<siz;i++)//complement
            {
                num[i]=9-num[i];
            }
            num[0]++;
            for(int i=1;i<siz;i++)//carry
            {
                num[i]+=num[i-1]/10;
                num[i-1]%=10;
            }
        }
        for(int i=104;i>=0;i--)
        {
            if(num[i]!=0)
            {
                p=i+1;
                break;
            }
            else if(i==0) p=0;
        }
        return IsSeventeen(num,p);
    }
}
int main()
{
    seventeen[0]=7;
    seventeen[1]=1;
    string s;
    while(cin>>s && s!="0")
    {
        int num[105]={0};
        int p=0;
        for(int i=s.size()-1;i>=0;i--)
        {
            num[p++]=s[i]-48;
        }
        cout<<IsSeventeen(num,p)<<endl;
    }
    return 0;
}

[UVA] 10140 - Prime Distance

/*20141108 hanting*/
#include <iostream>
#include <cmath>
#include <sstream>
using namespace std;
bool Num[100000];
int prime[10000];
int x=0;
bool isprime(unsigned int num)
{
    if(num<100000) return Num[num]==0 ? 1:0;
    int s=sqrt(num);//另存s//在for迴圈會慢
    for(int i=0;prime[i]<=s;i++)
    {
        if(num%prime[i]==0) return 0;
    }
    return 1;
}
int main()
{
    for(unsigned int i=2;i<100000;i++) Num[i]=0;
    Num[1]=1;
    for(unsigned int i=2;i<100000;i++)
    {
        if(!Num[i])
        {
            prime[x++]=i;
            for(unsigned int j=i*2;j<100000;j+=i)
            {
                Num[j]=1;
            }
        }
    }
    unsigned int L,U;
    string s;
    while(getline(cin,s))
    {
        stringstream sin(s);
        sin>>L>>U;
        unsigned int l,u;
        for(l=L;!isprime(l);l++);
        L=l;
        for(u=U;!isprime(u);u--);
        U=u;
        if(L>=U) cout<<"There are no adjacent primes."<<endl;
        else
        {
            int clos1=L,clos2=L,dis1=L,dis2=L;
            int temp1=L,temp2=L;
            int mini=U-L+1,maxi=0;
            unsigned int i;
            if(L==2) i=L+1;
            else i=L+2;
            for( i;i<=U;i+=2)
            {//質數一定是6n+1或6n-1，所以+2+4+2+4判斷增加效率
                if(isprime(i))
                {
                    temp1=temp2;
                    temp2=i;
                    if(temp2-temp1<mini)
                    {
                        clos1=temp1;
                        clos2=temp2;
                        mini=clos2-clos1;
                    }
                    if(temp2-temp1>maxi)
                    {
                        dis1=temp1;
                        dis2=temp2;
                        maxi=dis2-dis1;
                    }
                }
                if((i-1)%6==0) i+=2;//+4
            }
            cout<<clos1<<","<<clos2<<" are closest, "<<dis1<<","<<dis2<<" are most distant."<<endl;
        }
    }
    return 0;
}

[UVA] 369 - Combinations

/*20141107 hanting*/
#include <iostream>
using namespace std;
int prime[30];
int factor[100]={0};
int x=0;
void part1(int num)
{
    for(int i=0;num!=1;i++)
    {
        while(num%prime[i]==0)
        {
            factor[prime[i]]++;
            num/=prime[i];
        }
    }
}
void part2(int num)
{
    for(int i=0;num!=1;i++)
    {
        while(num%prime[i]==0)
        {
            factor[prime[i]]--;
            num/=prime[i];
        }
    }
}
void mul(int* ans,int n)
{
    for(int i=0;i<100;i++)
    {
        ans[i]*=n;
    }
    for(int i=1;i<100;i++)
    {
        ans[i]+=ans[i-1]/10;
        ans[i-1]%=10;
    }
}
void output(int *ans)
{
    int i;
    for(i=99;i>=0;i--)
    {
        if(ans[i]!=0) break;
    }
    for(int j=i;j>=0;j--)
    {
        cout<<ans[j];
    }
}
int main()
{
    int Num[100]={0};
    for(int i=2;i<100;i++)
    {
        if(Num[i]==0)
        {
            prime[x++]=i;
            for(int j=i;j<100;j+=i) Num[j]=1;
        }
    }
    int n,m;
    while(cin>>n>>m && n+m)
    {
        for(int i=0;i<100;i++) factor[i]=0;
        cout<<n<<" things taken "<<m<<" at a time is ";
        int ans[100]={1};
        if(m>n/2) m=n-m;;
        for(int i=2;i<=m;i++)
        {
            part2(i);
        }
        for(int i=n;m--;i--)
        {
            part1(i);
        }
        for(int i=2;i<98;i++)
        {
            while(factor[i]--)
            {
                mul(ans,i);
            }
        }
        output(ans);
        cout<<" exactly."<<endl;
    }
    return 0;
}


================================================

# /* 題目: UVa 369 - Combinations
#  * onlinejudge.org/external/3/369.pdf
#  * Language: Python
#  * Created on: 2019年12月19日
#  *   Author: hanting
#  */
def C(a, b):
    if a-b < b :
        b = a-b
    result = 1
    w = 1
    for i in range(a-b+1, a+1):
        result *= i
        result //= w
        w += 1
    return result
while(True):
    x, y = map(int, input().split())
    if [x, y] == [0, 0]:
        break
    print('{} things taken {} at a time is {} exactly.'.format(x, y, C(x, y)))



[UVA] 10303 - How Many Trees ?

/*20141102 hanting*/
/*因為WA不知道錯哪，所以另外又寫了一個版本，
   後來發現存大數用10000會溢位，1000就AC了*/

/*遞迴+重載運算*/
#include <iostream>
#include <vector>
using namespace std;
struct BigNum
{
    vector<int> num;
    void operator+=(BigNum n)
    {
        int R=max(n.num.size(),num.size());
        num.resize(R+1);
        n.num.resize(R+1);
        vector<int> ans(1);
        for(int i=0;i<R;i++)
        {
            ans[i]+=num[i]+n.num[i];
            ans.push_back(ans[i]/1000);
            ans[i]%=1000;
        }
        if(!ans[R]) ans.pop_back();
        num=ans;
    }
    BigNum operator*(BigNum n)
    {
        BigNum ans;
        ans.num.resize(num.size()+n.num.size());
        for(int i=0;i<num.size();i++)
        {
            for(int j=0;j<n.num.size();j++)
            {
                ans.num[i+j]+=num[i]*n.num[j];
            }
        }
        for(int i=1;i<ans.num.size();i++)
        {
            ans.num[i]+=ans.num[i-1]/1000;
            ans.num[i-1]%=1000;
        }
        for(int i=ans.num.size()-1;i>0;i--)
        {
            if(ans.num[i]==0) ans.num.pop_back();
            else break;
        }
        return ans;
    }
    void operator*=(int n)
    {
        vector<int> ans(1);
        for(int i=0;i<num.size();i++)
        {
            ans[i]+=num[i]*2;
            ans.push_back(ans[i]/1000);
            ans[i]%=1000;
        }
        if(!ans[ans.size()-1]) ans.pop_back();
        num=ans;
    }
    friend ostream& operator<<(ostream& out, BigNum& n)
    {
        int first=n.num.size()-1;
        out<<n.num[first];
        for(int i=first-1;i>=0;i--)
        {
            if(n.num[i]<100) out<<0;
            if(n.num[i]<10) out<<0;
            out<<n.num[i];
        }
        return out;
    }
};
BigNum store[1005];
BigNum tree(int n)
{
    if(store[n].num.size()) return store[n];
    else
    {
        for(int i=0;i<n/2;i++)
        {
            store[n]+=tree(i)*tree(n-i-1);
        }
        store[n]*=2;
        if(n%2==1)store[n]+=tree(n/2)*tree(n/2);
        return store[n];
    }
}
int main()
{
    store[0].num.push_back(1);
    store[1].num.push_back(1);
    store[2].num.push_back(2);
    store[3].num.push_back(5);
    int N;
    while(cin>>N)
    {
        tree(N);
        cout<<store[N]<<endl;
    }
    return 0;
}

/*vector+函數*/
#include <iostream>
#include <vector>
using namespace std;
vector<int> add(vector<int>,vector<int>);
vector<int> mul(vector<int>,vector<int>);
void output(vector<int>);
int main()
{
    int N;
    vector<int> num[1005];
    num[0].push_back(1);
    num[1].push_back(1);
    num[2].push_back(2);
    int MAX=2;
    while(cin>>N)
    {
        if(N<=MAX) output(num[N]);
        else
        {
            for(++MAX;MAX<=N;MAX++)
            {
                for(int i=0;i<MAX/2;i++)
                {
                    num[MAX]=add(num[MAX],mul(num[i],num[MAX-1-i]));
                }
                num[MAX]=mul(num[MAX],num[2]);
                if(MAX%2)
                {
                    num[MAX]=add(num[MAX],mul(num[MAX/2],num[MAX/2]));
                }
            }
            output(num[--MAX]);
        }
    }
    return 0;
}
vector<int> mul(vector<int> a,vector<int> b)
{
    vector<int> Result(a.size()+b.size());
    for(int i=0;i<a.size();i++)
    {
        for(int j=0;j<b.size();j++)
        {
            Result[i+j]+=a[i]*b[j];
        }
    }
    for(int i=1;i<Result.size();i++)
    {
        Result[i]+=Result[i-1]/1000;
        Result[i-1]%=1000;
    }
    for(int i=Result.size()-1;i>=0;i--)
    {
        if(!Result[i]) Result.pop_back();
        else break;
    }
    return Result;
}
vector<int> add(vector<int> a,vector<int> b)
{
    vector<int> Result;
    int Resize=max(a.size(),b.size());
    a.resize(Resize);
    b.resize(Resize);
    for(int i=0;i<a.size();i++)
    {
        Result.push_back(a[i]+b[i]);
    }
    Result.push_back(0);
    for(int i=1;i<Result.size();i++)
    {
        Result[i]+=Result[i-1]/1000;
        Result[i-1]%=1000;
    }
    if(!Result[Result.size()-1]) Result.pop_back();
    return Result;
}
void output(vector<int> N)
{
    for(int i=N.size()-1;i>=0;i--)
    {
        if(i!=N.size()-1&&N[i]<100) cout<<"0";
        if(i!=N.size()-1&&N[i]<10) cout<<"0";
        cout<<N[i];
    }
    cout<<endl;
}