近期简单题目小结 UVA 100+HDU 2007+URAL 1084+Poj 1152+UVA 10042+UVA 11752+UVA 10780

我不是女神ヾ 2022-08-24 14:18 148阅读 0赞

新年练习赛(http://acm.hust.edu.cn/vjudge/contest/view.action?cid=40140\#overview密码password)和之前的几题。

这场比赛卡在一道很水的大数题，不能更逗。。到现在我都还没看出来哪里错了，关键是赛后我发现同一段代码Poj能过，Uva就过不了……只能说技艺不精。于是下定决心学java，最近也做了几题，有时间再总结下。

**UVA 100 The 3n + 1 problem**

这题的坑点是区间端点 i有可能大于j

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    const int N=1000005;
    int a[N];
    
    int Cal (int k,int m)
    {
        m++;
        if (k==1) return m;
        if (k%2==1) return Cal(3*k+1,m);
        else return Cal(k/2,m);
    }
    
    int main ()
    {
        int i,j,m,n,k;
        while (~scanf("%d%d",&m,&n))
        {
            bool flag=false;
            if (m>n)
                flag=true,swap(m,n);
            for (k=0,i=m;i<=n;i++)
            {
                if (a[i]==0)
                    a[i]=Cal(i,0);
                if (a[i]>k)
                    k=a[i];
            }
            if (flag)
                swap(m,n);
            printf("%d %d %d\n",m,n,k);
        }
    }

HDU 2007 平方和与立方和

#include <cstdio>
    #include <algorithm>
    using namespace std;
    
    int main ()
    {
        int n,m;
        while (~scanf("%d%d",&m,&n))
        {
            if (m>n)
                swap (m,n);
            int sum1=0,sum2=0;
            for (int i=m;i<=n;i++)
            {
                if (i%2==0)
                    sum1+=i*i;
                else
                    sum2+=i*i*i;
            }
            printf("%d %d\n",sum1,sum2);
        }
        return 0;
    }

**URAL 1084 Goat in the Garden**

#include <cmath>
    #include <cstdio>
    
    const double PI=acos(-1.0);
    
    int main ()
    {
        double len,R;
        double tri1,tri2,are1,are2;
        while (~scanf("%lf%lf",&len,&R))
        {
            if (R<=len/2)
                printf("%.3lf\n",PI*R*R);
            else if (sqrt(2.0)*len <= 2*R)
                printf("%.3lf\n",len*len);
            else
            {
                tri1=acos(len/2/R);
                tri2=PI/2-2*tri1;
                are1=tri2*R*R/2;
                are2=len*len/4*tan(tri1);
                printf("%.3lf\n",4*(are1+are2));
            }
        }
        return 0;
    }

**UVA 10093 & Poj 1152 An Easy Problem!**

题意：给定一个未知进制下的数,找到x进制,使得这个数整除x-1

摘一段Poj Discuss里的推导

设输入的是abcd，假设其解是n进制，则有  
（a\*n\*n\*n + b\*n\*n + c\*n + d)%(n-1)=0  
则有：( (a\*n\*n\*n)%(n-1)+  
(b\*n\*n)%(n-1)+  
(c\*n)%(n-1)+  
d )%(n-1)=0  
则有：（ (a\* (n%(n-1)) \*(n%(n-1)) \*(n%(n-1)))+  
(b\* (n%(n-1)) \*(n%(n-1)))+  
(c\* (n%(n-1) +  
d ) %(n-1)=0  
则有: (a\*1\*1\*1+b\*1\*1+c\*1+d)%(n-1)=0  
则有：(a+b+c+d)%(n-1)=0

#include <cstdio>
    #include <ctype.h>
    #include <cstring>
    #define upmax(a,b) ((a)=(a)>(b)?(a):(b))
    
    char str[1000005];
    int limit;
    
    int Cal ()
    {
        int ans=0,tmp;
        int len=strlen(str);
        for (int i=0;i<len;i++)
        {
            if (isdigit(str[i])) tmp=str[i]-'0';
            else if (islower(str[i])) tmp=(str[i]-'a')+36;
            else if (isupper(str[i]))tmp=(str[i]-'A')+10;
            limit=upmax(limit,tmp);
            ans+=tmp;
        }
        return ans;
    }
    
    int main ()
    {
        while (~scanf("%s",str))
        {
            limit=-1;
            int sum=Cal(),i;
            if (limit==0) limit=1;
            for (i=limit;i<62;i++)
                if (sum%i==0)
                    break;
            if (i>=62)
                printf("such number is impossible!\n");
            else
                printf("%d\n",i+1);
        }
        return 0;
    }

**UVA 10042 Smith Numbers**

题意：若一个合数的质因数分解式逐位相加之和等于其本身逐位相加之和，则称这个数为Smith数，求比输入n大的第一个Smith数。

#include <cstdio>
    #include <cstring>
    
    const int N=100005;
    int prime[70000],np=0;
    bool tag[N];
    
    void Prime ()
    {
        for (int i=2;i<N;i++) if (tag[i] == false)
        {
            prime[np++]=i;
            for (int j=i+i;j<N;j+=i)
                tag[j]=true;
        }
    }
    
    int Caldigit (int n)
    {
        int sum=0;
        while (n)
        {
            sum+=n%10;
            n/=10;
        }
        return sum;
    }
    
    bool Judge (int n)
    {
        int sum=0,tmp=n;
        bool flag=false;
        for (int i=0;(long long) prime[i]*prime[i]<=n;i++)
            while(n%prime[i]==0)
            {
                flag==true;
                sum+=Caldigit(prime[i]);
                n/= prime[i];
            }
        //要求合数
        if (n!=1 && n!=tmp)
            sum+=Caldigit(n);
        if (sum==Caldigit(tmp))
            return true;
        else
            return false;
    }
    
    int main ()
    {
        int T,n;
        scanf("%d",&T);
        Prime();
        while (T--)
        {
            scanf("%d",&n);
            n++;
            while (Judge(n)==false)
               n++;
            printf ("%d\n",n);
        }
        return 0;
    }

**UVA 11752 The Super Powers**

题意：求出所有小于2^64-1的Super Powers，一个数n是Super Powers当 a^i=b^j=n  
思路：显然，super powers的幂指数一定是和数

#include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <set>
    using namespace std;
    
    #define i64u unsigned long long
    
    int heshu[50]={4,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28
                ,30,32,33,34,35,36,38,39,40,42,44,45,46,48,49,50,51,52,54,55,56,57,58,60,62,63,64};
    
    i64u POW (i64u s,i64u index)
    {
        i64u ans=1;
        while (index>=1)
        {
            if ((index&1)==1)   //奇数
                ans=(ans*s);
            index>>=1;
            s=s*s;
        }
        return ans;
    }
    set<i64u> s;
    
    int main ()
    {
        int id=0,i;
        printf("1\n");
        for (i=2;i<65536;i++)
        {
            int limit;
            if (i==2) limit=63;
            else limit=ceil( 64/(log(i)/log(2)) )-1;
            if (limit <4) break;
            for (int j=0;heshu[j]<=limit;j++)
                s.insert(POW(i,heshu[j]) );
        }
        set<i64u>::iterator it;
        for (it=s.begin();it!=s.end();it++)
            printf("%llu\n",*it);
        return 0;
    }

**UVA 10780 Again Prime? No Time.**  
题意：给出m,n,使m^x整除n!,求x

思路：假设m=P1^k1 \* P2^k2 \* P3^k3 \*...\* Pm^km，问题转化为求n！分解质因数后P1、P2....Pm的指数是多少。

#include <iostream>
    #include <cstdio>
    using  namespace std;
    int getsum(int n,int x)
    {
        int ans=0;
        while(n)
        {
            ans+=n/x; n/=x;
        }
        return ans;
    }
    int main()
    {
        int t,n,m,j=1;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d",&m,&n);
            int i=2,num=0,sum,ans=1000000;
            while(m>1)
            {
                num=0;
                while(m%i==0)
                {
                    num++;
                    m/=i;
                }
                if(num)
                {
                    sum=getsum(n,i)/num;
                    if(ans>sum) ans=sum;
                }
                i++;
            }
    
            if(ans!=0)
                printf("Case %d:\n%d\n",j++,ans);
            else
                printf("Case %d:\nImpossible to divide\n",j++);
    
        }
        return 0;
    }