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 ZxyElf at 2013-06-13 13:39:42 on Problem 1604
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

int t2[10001],t5[10001],te[10001];

int quickpow(int a,int b,int c){
	if (b==0) return 1;
	else if (b==1) return  a%c;
	else return quickpow(a,b/2,c)*quickpow(a,b-b/2,c)%c;
}

void gen(){
	int i,j,k;
	for (i=1;i<=10000;i++){
		if (i%2) t2[i]=t2[i-1];
		else{
			for (k=2,j=4;j<=i && i%j==0;k++,j*=2);
			t2[i]=t2[i-1]+k-1;
		}
	}

	for (i=1;i<=10000;i++){
		if (i%5) t5[i]=t5[i-1];
		else{
			for (k=2,j=25;j<=i && i%j==0;k++,j*=5);
			t5[i]=t5[i-1]+k-1;
		}
	}

	te[1]=1;
	for (i=2;i<=10000;i++){
		int j=i;
		while (j%2==0)j/=2;
		while (j%5==0)j/=5;
		te[i]=te[i-1]*j%10;
	}

}


int main()
{
	int n;
	gen();
	while (cin>>n){
		cout.width(5);
		int ans=te[n]*quickpow(2,t2[n]-t5[n],10)%10;
		cout<<right<<n<<" -> "<<ans<<endl;
	}
	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