NOJ 212題K尾等数

1955 ワード

タイトルリンク~>
この問題は簡単な問題で、ブログに書こうとは思わなかったが、他の人の優コードを見て、そんな方法がいいとは思わなかった.私が使っている高速べき乗はそれから遍歴を始めて、时間は考えられます...
コード(本人):
#include<stdio.h>
int pow(int b,int m)// 
{
    int ans=1;
    while(b)
    {
        if(b%2)
        {
           ans=(m*ans)%1000;
        }
        b/=2;
        m=(m*m)%1000;
    }
    return ans;
}
int pss(int b,int n)
{
    int ans=1;
    while(b)
    {
        if(b%2)
        {
           ans=n*ans;

        }
        b/=2;
        n=n*n;
    }
    return ans;
}
int main()
{
    int T;
    long long m;
    int i,j,k,x,y,q;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld",&m);
         if(m<1000)// 1000
           {
               q=m;
               for(i=1;i<=35;i++)
                 if(pss(i,q)>=1000)
                  break;
           }
         else {
                q=m%1000;
                i=1;
              }
          for(j=i;j<1000;j++)
             {
                  int f=0;
                  for(k=i;k<j;k++)
                  {
                       x=pow(j,q);
                       y=pow(k,q);
                       if(x==y)
                        {
                            f=1;
                            break;
                        }
                   }
              if(f==1)
                 break;
             }
        printf("%d
",j+k); } return 0; }

コード(優):
#include<stdio.h>
int main()
{
    long int n,k,i;
    scanf("%d",&n);
	while(n--)
	{
		scanf("%d",&k);
        long int a[1000]={0},t,flag=0;
        if(k>=1000)
		{
			k%=1000;
		    a[k]++;
		    flag=1;
		}
        for(t=k,i=2;;i++)
		{
			   k=t*k;
            if(flag==1||k>=1000)
			{
				k%=1000;
				a[k]+=i;
				if(a[k]>i)// 
					break;
			}
		}
        printf("%d
",a[k]); } }