Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

囧了,自己乱写居然过了。。。

Posted by a470086609 at 2009-09-04 23:11:33 on Problem 3406
大家看看这样写貌似不对吧。。。

#include<stdio.h>

int n,m;
int div[10][10];
const int di[20][3]={{1,1,1},{3,1,3},{7,1,7},{9,1,9},
{1,3,7},{1,7,3},{1,9,9},
{3,3,1},{3,7,9},{3,9,7},
{7,3,9},{7,7,1},{7,9,3},
{9,3,3},{9,7,7},{9,9,1}};

void add(int n,int d,int &sum,bool ad)      //计算n!里面包含多少个因子d
{
    while(d<=n)
    {
        if(ad)
            sum+=(n/=d);
        else
            sum-=(n/=d);
    }
}
//就是这里。。。下面函数本意是那样,但是貌似这样做不对,用100 10这组数据就不对了
void add2(int n,int &ans,bool add)          //计算n!除掉2和5之后的尾数,add时乘进ans中,false时ans/尾数。
{
    int i;
    for(;n>=20;n/=5)
    {
        for(i=n%20;i;i--)
        {
            if((i%5)&&(i%2))
            {
                if(add)ans*=i,ans%=10;
                else ans=div[ans%10][i%10];
            }
        }
    }
    for(i=n%20;i;i--)
    {
        int p=i;
        while(!(p%5))p/=5;
        while(!(p%2))p/=2;
        if(add) ans*=p,ans%=10;
        else ans=div[ans%10][p%10];
    }
}

void init2()
{
    for(int i=0;i<16;i++)
        div[di[i][0]][di[i][1]]=di[i][2];   
    //div[a][b]=c表示,a=b*c%10,即尾数为a的除以尾数为b的,等于尾数为c的(但是仅适用于a,b,c为(1,3,7,9)时)
}

int main()
{
    init2();
    //printf("%d %d %d %d\n",di[15][0],di[15][1],di[15][2],div[di[15][0]][di[15][1]]);
    while(scanf("%d%d",&n,&m)!=EOF)
    {
     /*   if(n==0&&n==0)
            printf("0\n");*/
        int i;
        int sum2=0,sum5=0,ans=1;
        //下面计算质因子2和5
        add(n,2,sum2,true);add(n,5,sum5,true);
        add(m,2,sum2,false);add(m,5,sum5,false);
        add(n-m,2,sum2,false);add(n-m,5,sum5,false);
     
        if(sum5>sum2)
        {
            printf("5\n");
            continue;
        }
        else
            sum2-=sum5;
        add2(n,ans,true);
        add2(m,ans,false);
        add2(n-m,ans,false);
        //下面乘上剩余的2
        if(sum2>=4) ans*=6,ans%=10;     //由于2*2*2*2=16,尾数为6,而6*6%10=6,所以无论存在多少个2,模4再乘上6即可
        for(i=sum2%4;i;i--)     //乘2
        {
            ans<<=1;
            ans%=10;
        }
        printf("%d\n",ans);
    }

    return 0;
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator